- 188

- 1

## Main Question or Discussion Point

given two integers A and B that are very big is there any 'fast' algorithm to calculate the remainder of the division [tex] \frac{A}{B} [/tex] or in other similar words to say if B divides or not A thanks.

- Thread starter mhill
- Start date

- 188

- 1

given two integers A and B that are very big is there any 'fast' algorithm to calculate the remainder of the division [tex] \frac{A}{B} [/tex] or in other similar words to say if B divides or not A thanks.

CRGreathouse

Science Advisor

Homework Helper

- 2,817

- 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
- 1K

- Last Post

- Replies
- 6

- Views
- 2K

- Last Post

- Replies
- 2

- Views
- 3K

- Last Post

- Replies
- 7

- Views
- 3K