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

    CRGreathouse

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Divisibility problem
  1. Fun Divisibility Problem (Replies: 14)

  2. Division ring (Replies: 0)

Loading...