Divisibility problem

  • Thread starter mhill
  • Start date
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.
 

Answers and Replies

CRGreathouse
Science Advisor
Homework Helper
2,817
0
How big? Are the numbers likely to have small prime factors?



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.
 

Related Threads for: Divisibility problem

  • 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
Top