Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Divisibility problem

  1. Apr 16, 2008 #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.
  2. jcsd
  3. Apr 16, 2008 #2


    User Avatar
    Science Advisor
    Homework Helper

    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook