- #1

- 188

- 1

- Thread starter mhill
- Start date

- #1

- 188

- 1

- #2

CRGreathouse

Science Advisor

Homework Helper

- 2,820

- 0

For numbers under 100 digits, any reasonable program can do the calculation 'in the blink of an eye'.

Newton's method can be used to divide two numbers in time [itex]O(n^{1.585})[/itex] using Karatsuba multiplication.

For truly huge numbers (10,000 to 100,000 or more digits), FFT-based multiplication algorithms like Strassen's algorithm or the new Furer's algorithm provide quasilinear division using Newton's method.

I don't know of the success, in general, of higher-order methods for division, but I can't imagine any can outdo the [itex]O(n\log n\log\log n)[/itex] of the FFT methods I mentioned.

- Last Post

- Replies
- 14

- Views
- 4K

- Last Post

- Replies
- 3

- Views
- 3K

- Replies
- 8

- Views
- 4K

- Last Post

- Replies
- 1

- Views
- 2K

- Last Post

- Replies
- 1

- Views
- 2K

- Last Post

- Replies
- 6

- Views
- 2K

- Last Post

- Replies
- 7

- Views
- 4K

- Last Post

- Replies
- 2

- Views
- 3K

- Last Post

- Replies
- 2

- Views
- 3K

- Last Post

- Replies
- 2

- Views
- 2K