Friday, June 7, 2013

Modulus algorithm

Suppose you want to see if 897354 divides 54
the leading eight of 897354 has 5 digits to the right of it, so looking at the fraction 8/54
.14814814 we can just look at the fractional part when this decimal is shifted to the right 5 places
14814.814 and just the part to the right of the decimal is .814 (rounded to thousandths)
The 9 in 897354 has 4 digits to the right of it so 9/54 is:
.166666 and shifting the decimal 4 digits to the right and dropping the whole number part is .666
so so far we have .814, .666 and doing the same thing for the rest is .63, .555, .925, .074
A fast way to do find these numbers is to calculate 1/54 and then multiply by 8,9,7,3,5,4
We can add these 5 numbers and get: 3.664 the part to the right of the decimal is .664 which is within a couple thousands of the remainder when 897354 dividing 54 = .666 so 897354 does not divide 54 (it has a remainder of 2/3rds.

The nice thing about this algorithm is it takes a process that is usually serial in nature, division you usually do long division from left to right and makes it parallel, if you had 10,000 digits of a number you were dividing you could send to 10,000 computers for example if the 573rd digit was 9,
573, 9, 4714
which would tell it return the 573rd place of the decimal 9/4714:see section B,   and it would return something and then one thread could add up all the returned numbers to find out whether the 10,000 digit number divides 4714.

-B- to be completed

No comments:

Post a Comment