"Easy" modulo???
mike3
(posting to both comp.programming and sci.math because this is both a
programming and math-related issue)
I heard that it is "easier" to reduce modulo some prime numbers, like
2^64 - 2^32 + 1 (FFFFFFFF00000001 in hexadecimal, 18446744069414584321
in decimal) than others. Although the bit patterns in the number I
gave there are certainly nice and simple, they don't immediately
suggest a method to reduce something with. Is division by numbers of
this form (2^n - 2^m + 1, n > m > 0) somehow easier due to the bits,
or the simple polynomial expansion? How do you do that "easy" divide
or modulo, anyway?
akakiyak...@gmail.com
I don't know if this is you're looking for...
Using little Fermat theorem (*) you can reduce the size of the
exponent:
For a and p such that gcd(a, p) = 1, is true that a^(p-1) = 1 (mod p)
2^64 is coprime with every prime number greater than 2 (the only
factors are powers of 2)
If you want to know 2^64 (mod 11) for example
64 = 10x6 + 4
then
2^64 = 2^(10x6 + 4) = 2^(10x6) + 2^4 = (2^10)^4 x 2^4 ={using (*)} 1 x
2^4 = 16 = 5 (mod 11)
So if you need 2^64 (mod p) (p prime > 2) you divide 64 by p-1 and get
the remainder r, and the 2^64 is congruent to 2^r modulo p.
Then you can use 2^n - 2^m + 1 (mod p) = (2^n (mod p) - 2^m (mod p) +
1) (mod p)
In fact the theorem is a^p = a (mod p) for p prime, but if gcd(a,p) =
1 then a is invertible in Z*p and this result may be better for your
algorithm.
A
mike3
But this doesn't really seem to address -- how does one
"easily" _reduce something modulo_ _2^n - 2^m + 1_?
Bill Dubuque
>
> I heard that it is "easier" to reduce modulo some prime numbers, like
> 2^64 - 2^32 + 1 (FFFFFFFF00000001 in hexadecimal, 18446744069414584321
> in decimal) than others. Although the bit patterns in the number I
> gave there are certainly nice and simple, they don't immediately
> suggest a method to reduce something with. Is division by numbers of
> this form (2^n - 2^m + 1, n > m > 0) somehow easier due to the bits,
> or the simple polynomial expansion? How do you do that "easy" divide
> or modulo, anyway?
HINT x^2 = x-1 -> x^3 = -1, x^4 = -x, x^5 = 1-x, x^6 = 1
-> d := d0 + d1 x + d2 x^2 + d3 x^3 + d4 x^4 + d5 x^5 + d6 x^6
= d0-d2-d3+d5+d6 + (d1+d2-d4-d5) x (mod x^2 - x + 1)
E.g.
x=10,d=6543210 = 0 -2 -3 +5 +6 + ( 1 +2 -4 -5)10 = 6-60 = -54 = 37 (mod 91)
Indeed 6543210 = 37 + 91 * 71903. For your application put x = 2^32.
--Bill Dubuque
Bill Dubuque
i.e. a := d0 - d3 + d6 - d9 + d12 - d15 + ...
b := d1 - d4 + d7 - d10 + d13 - d16 + ...
c := d2 - d5 + d8 - d11 + d14 - d17 + ...
-> Sum di x^i = a-c + (b+c) x (mod x^2 - x + 1)
This is casting out 91's (like casting out 9's / nines)
or casting out (b-1)b+1's = b-1,1 (radix b)
= FFFFFFFF,00000001 (radix 2^32)
--Bill Dubuque
mike3
That's sort of what I figured, but when you have x = 2^32, and d4, d5,
d6
all equal to 0 (so d3, d2, d1, d0 are the "digits" of the 128 bit
result I
want to reduce), you get d0-d2-d3 + (d1+d2)x, yet for reducing
the number with d3 = d2 = d1 = d0 = 2^32 - 1 (largest possible
"digit") --
ie. 2^128 - 1 in base 2^32, we get something LARGER than our modulus:
36,893,488,138,829,168,640 (or in base 2^32 represented with hex,
1 FFFFFFFE 00000000). So what do you do?
Michael Press
Bill Dubuque <w...@nestle.csail.mit.edu> wrote:
Note that while mike3 restricted the modulus to prime numbers
you did not use this assumption.
--
Michael Press
Michael Press
<1187030823....@g12g2000prg.googlegroups.com>,
mike3 <mike...@yahoo.com> wrote:
Reduce again.
1 FFFFFFFE 00000000 = x^2 + FFFFFFFE.x + 0
d1 = FFFFFFFE, d2 = 1, dk = 0 otherwise.
1 FFFFFFFE 00000000 = (FFFFFFFE + 1)x - 1
= FFFFFFFF.x - 1
= FFFFFFFF.2^32 - 1
= FFFFFFFE FFFFFFFF (Mod 2^64 - 2^32 + 1).
--
Michael Press
mike3
> In article
> <1187030823.319023.54...@g12g2000prg.googlegroups.com>,
You mean you've got to apply that thing TWICE?
Is twice the maximum number of times though? (I'd guess
so, since 'FFFFFFFF' 'FFFFFFFF' 'FFFFFFFF' 'FFFFFFFF'_4294967296
is the largest possible 128 bit number.) Also,
can the extra digit be any higher than 1?
> --
> Michael Press
Michael Press
<1187129733....@q3g2000prf.googlegroups.com>,
mike3 <mike...@yahoo.com> wrote:
Keep applying until the result is less than the modulus.
How many times do you cast nines out of
301404115361098524298988452879098721467446959901936564415804800345729\
442752974105153164104241789364081480629211227908029559019249113005445\
04493393940583330407823851967038836235846755854148813031384754669479
--
Michael Press
Bill Dubuque
>>>>
>>>> I heard that it is "easier" to reduce modulo some prime numbers, like
>>>> 2^64 - 2^32 + 1 (FFFFFFFF00000001 in hexadecimal, 18446744069414584321
>>>> in decimal) than others. Although the bit patterns in the number I
>>>> gave there are certainly nice and simple, they don't immediately
>>>> suggest a method to reduce something with. Is division by numbers of
>>>> this form (2^n - 2^m + 1, n > m > 0) somehow easier due to the bits,
>>>> or the simple polynomial expansion? How do you do that "easy" divide
>>>> or modulo, anyway?
>>>
>>> HINT x^2 = x-1 -> x^3 = -1, x^4 = -x, x^5 = 1-x, x^6 = 1
>>>
>>> -> d := d0 + d1 x + d2 x^2 + d3 x^3 + d4 x^4 + d5 x^5 + d6 x^6
>>>
>>> = d0-d2-d3+d5+d6 + (d1+d2-d4-d5) x (mod x^2 - x + 1)
>>> E.g.
>>>
>>> Indeed 6543210 = 37 + 91 * 71903. For your application put x = 2^32.
>>
>> all equal to 0 (so d3, d2, d1, d0 are the "digits" of the 128 bit result
>> I want to reduce), you get d0-d2-d3 + (d1+d2)x, yet for reducing the
>> number with d3 = d2 = d1 = d0 = 2^32 - 1 (largest possible "digit") --
>> ie. 2^128 - 1 in base 2^32, we get something LARGER than our modulus:
>> 36,893,488,138,829,168,640 (or in base 2^32 represented with hex,
>> 1 FFFFFFFE 00000000). So what do you do?
>
> Reduce again.
> 1 FFFFFFFE 00000000 = x^2 + FFFFFFFE.x + 0
> d1 = FFFFFFFE, d2 = 1, dk = 0 otherwise.
>
> 1 FFFFFFFE 00000000 = (FFFFFFFE + 1)x - 1
> = FFFFFFFF.x - 1
> = FFFFFFFF.2^32 - 1
> = FFFFFFFE FFFFFFFF (Mod 2^64 - 2^32 + 1).
Rather than iteratively applying the reduction formula as above,
it is usually more efficient to simply replace the carries into
the 3rd digit (coef of x^2) as they arise, via x^2 -> x - 1
i.e. add one to the second digit and subtract one from the first.
With care, the entire calculation can be performed using only
double-precision numbers (or single's with slightly more effort).
These remarks apply to computer algorithms. For hand calculation
it may be more convenient to actually use pseudo-triple-precision,
i.e. accumulate the carries, then finally reduce them all at once,
or whenever may prove most convenient (e.g. to avoid borrowing).
As I said this is simply casting out 91's (or b-1,1's in radix b),
and just as in casting out 9's, one needs to perform normalizations
to reduce the results to the canonical range. But this can be done
using only additions and subtractions - no divisions are required.
--Bill Dubuque
Bill Dubuque
>
> Keep applying [casting 91's] until the result is less than the modulus.
> 301404115361098524298988452879098721467446959901936564415804800345729\
> 442752974105153164104241789364081480629211227908029559019249113005445\
> 04493393940583330407823851967038836235846755854148813031384754669479
I cast out nines only once, simply adding the digits (mod 9).
It would be much more inefficient to instead add the digits in Z,
and apply the method iteratively - as you seem to propose above.
One should view this method simply as checking equations in Z
by checking them in finite images Z/m of Z, i.e. modulo m.
It just so happens the the modular image is easy to compute
if the radix b is an nth root of 1 in Z/m, b^n = 1 (mod m),
or other similar simple forms.
--Bill Dubuque
Phil Carmody
> Michael Press <rub...@pacbell.net> wrote:
> >
> > Keep applying [casting 91's] until the result is less than the modulus.
> > How many times do you cast nines out of
> > 301404115361098524298988452879098721467446959901936564415804800345729\
> > 442752974105153164104241789364081480629211227908029559019249113005445\
> > 04493393940583330407823851967038836235846755854148813031384754669479
>
> I cast out nines only once, simply adding the digits (mod 9).
> It would be much more inefficient to instead add the digits in Z,
> and apply the method iteratively - as you seem to propose above.
Not always. It's a common optimisation to combine in Z and only map
back to Z/nZ when necessary (typically when you are about to exceed
the size for atomic operations). For additions, that can be a whole
load of operations.
Phil
--
Dear aunt, let's set so double the killer delete select all.
-- Microsoft voice recognition live demonstration
mike3
> Michael Press <rub...@pacbell.net> wrote:
How does adding and subtracting 1 from the second and first digits,
respectively, make it work? And do you do this all the time or do
you have to detect that "carry" somehow?
Bill Dubuque
>Bill Dubuque <w...@nestle.csail.mit.edu> writes:
>>Michael Press <rub...@pacbell.net> wrote:
>>>
>>> Keep applying [casting 91's] until the result is less than the modulus.
>>> How many times do you cast nines out of
>>> 301404115361098524298988452879098721467446959901936564415804800345729\
>>> 442752974105153164104241789364081480629211227908029559019249113005445\
>>> 04493393940583330407823851967038836235846755854148813031384754669479
>>
>> I cast out nines only once, simply adding the digits (mod 9).
>> It would be much more inefficient to instead add the digits in Z,
>> and apply the method iteratively - as you seem to propose above.
>
> Not always. It's a common optimisation to combine in Z and only map
> back to Z/nZ when necessary (typically when you are about to exceed
> the size for atomic operations). For additions, that can be a whole
> load of operations.
But here we are specifically discussing casting out nines,
hence hand or mental calculations - not computer calculations
It'd be quite frivolous to cast out 9's on a modern computer.
As for computer implementations, see my prior remarks here.
--Bill Dubuque
Phil Carmody
> Phil Carmody <thefatphi...@yahoo.co.uk> wrote:
> >Bill Dubuque <w...@nestle.csail.mit.edu> writes:
> >>Michael Press <rub...@pacbell.net> wrote:
> >>>
> >>> Keep applying [casting 91's] until the result is less than the modulus.
> >>> How many times do you cast nines out of
> >>> 301404115361098524298988452879098721467446959901936564415804800345729\
> >>> 442752974105153164104241789364081480629211227908029559019249113005445\
> >>> 04493393940583330407823851967038836235846755854148813031384754669479
> >>
> >> I cast out nines only once, simply adding the digits (mod 9).
> >> It would be much more inefficient to instead add the digits in Z,
> >> and apply the method iteratively - as you seem to propose above.
> >
> > Not always. It's a common optimisation to combine in Z and only map
> > back to Z/nZ when necessary (typically when you are about to exceed
> > the size for atomic operations). For additions, that can be a whole
> > load of operations.
>
> But here we are specifically discussing casting out nines,
> hence hand or mental calculations - not computer calculations
I don't see that implication. The algorithm is casting out nines
whether it's done by hand or computer.
And if it is done by hand, then one digit is the size of atomic
operations, so my statement remains true.
> It'd be quite frivolous to cast out 9's on a modern computer.
That depends if you take "9" as being the literal number 9,
or a metaphor for B-1 where B is the base of representation.
If literal number 9, then it then depends on whether the
number is stored in a base-10-like representation or in
binary. I don't have the background in the thread to know
exactly what's being talked about. For example, if the number
is stored in BCD, then casting out 9s by accumulating large
numbers of sums before making a modular reduction makes
perfect sense, and isn't frivolous at all. But if it's
binary, then you probably want to cast out 63s instead.
> As for computer implementations, see my prior remarks here.
Ah OK. Your previous posts seem to have begun
<<<
mike3 <mike...@yahoo.com> wrote:
>>>
which means I've not read them. Maybe a leopard can change its
spots, but that one hit the killfile so convincingly that I've
not even read replies to him since.
Michael Press
Bill Dubuque <w...@nestle.csail.mit.edu> wrote:
But I did not do it mentally.
$ cat >/tmp/data
30140411536109852429898845287909872146744695990193656441580480034572944275297410515316410424178936408148062921122790802955901924911300544504493393940583330407823851967038836235846755854148813031384754669479
^D
$ perl -ne 'print qq/0 /, join(q/+/, split(//)), qq/p\n/' /tmp/data | dc
908
There are plenty of circumstances where it is better to
accumulate an intermediate result and limit the modulus reductions.
--
Michael Press
Bill Dubuque
Another method is to apply to the Horner form the rule
(ax+b)x+c = (a+b)x+c-a since x^2 = x - 1
c
or a, b ; a+b, c-a in tabular form
4 3 2 1 0
e.g. 6,5 ; 11,-2 ; 9,-8 ; 1,-7 ; -6,0 ; -6,6
/ / / / / /
(((((6x+5) x +4 ) x +3) x + 2 ) x +1) x + 0 (Horner)
-> 6543210 = {-6,6}_10 = -6(10)+6 = -54 = 37 (mod 91)
--Bill Dubuque
Bill Dubuque
>Bill Dubuque <w...@nestle.csail.mit.edu> writes:
>>Phil Carmody <thefatphi...@yahoo.co.uk> wrote:
>>>Bill Dubuque <w...@nestle.csail.mit.edu> writes:
>>>>Michael Press <rub...@pacbell.net> wrote:
>>>>>
>>>>> Keep applying [casting 91's] until the result is less than the modulus.
>>>>> How many times do you cast nines out of
>>>>> 301404115361098524298988452879098721467446959901936564415804800345729\
>>>>> 442752974105153164104241789364081480629211227908029559019249113005445\
>>>>> 04493393940583330407823851967038836235846755854148813031384754669479
>>>>
>>>> I cast out nines only once, simply adding the digits (mod 9).
>>>> It would be much more inefficient to instead add the digits in Z,
>>>> and apply the method iteratively - as you seem to propose above.
>>>
>>> Not always. It's a common optimisation to combine in Z and only map
>>> back to Z/nZ when necessary (typically when you are about to exceed
>>> the size for atomic operations). For additions, that can be a whole
>>> load of operations.
>>
>> But here we are specifically discussing casting out nines,
>> hence hand or mental calculations - not computer calculations
>
> I don't see that implication. The algorithm is casting out nines
> whether it's done by hand or computer. And if it is done by hand,
> then one digit is the size of atomic operations, so my statement
> remains true.
Above I am talking about mentally casting out 9's by simply
adding the digits considered as elts of the abstract ring Z/9,
i.e. by mentally accessing a memorized addition table of Z/9,
exactly the same way one does for addition of decimal digits.
So your advice to delay reductions (mod 9) is not relevant
since there are no reductions (but a neurally hardwired 9=0
normalization one applies while scanning the decimal digits).
In fact the reason I presented this method was precisely to
emphasize that not all methods of casting 9's work the way
that Mike (and now you) seem to think that they all should.
One could proceed as you advise, adding digits in Z, delaying
reductions (mod 9) until one exceeds say a few decimal digits.
But this would be much slower than working in Z/9, and more
error prone since it is of higher complexity - it requires
much more mental bookkeeping: a multiple digit accumulator,
carry propagation, reductions (mod 9), etc. Of course such
optimizations may prove useful for computer calculation but,
as I stressed above, here I'm specifically discussing mental
calculations - a classical application of casting out nines
(not to be confused with pencil and paper calculation, which
may be slightly more amenable to delaying modular reduction).
--Bill Dubuque
Bill Dubuque
>Bill Dubuque <w...@nestle.csail.mit.edu> wrote:
>>Phil Carmody <thefatphi...@yahoo.co.uk> wrote:
>>>Bill Dubuque <w...@nestle.csail.mit.edu> writes:
>>>>Michael Press <rub...@pacbell.net> wrote:
>>>>>
>>>>> Keep applying [casting 91's] until the result is less than the modulus.
>>>>> How many times do you cast nines out of
>>>>> 301404115361098524298988452879098721467446959901936564415804800345729\
>>>>> 442752974105153164104241789364081480629211227908029559019249113005445\
>>>>> 04493393940583330407823851967038836235846755854148813031384754669479
>>>>
>>>> I cast out nines only once, simply adding the digits (mod 9).
>>>> It would be much more inefficient to instead add the digits in Z,
>>>> and apply the method iteratively - as you seem to propose above.
>>>
>>> Not always. It's a common optimisation to combine in Z and only map
>>> back to Z/nZ when necessary (typically when you are about to exceed
>>> the size for atomic operations). For additions, that can be a whole
>>> load of operations.
>>
>> But here we are specifically discussing casting out nines,
>> hence hand or mental calculations - not computer calculations
>> It'd be quite frivolous to cast out 9's on a modern computer.
>> As for computer implementations, see my prior remarks here.
>
> But I did not do it mentally.
>
>
> $ perl -ne 'print qq/0 /, join(q/+/, split(//)), qq/p\n/' /tmp/data | dc
> 908
You both missed my point. Let's recap. I showed the OP how to compute
modular reductions (mod x^2-x+1), i.e. cast 91's, or b-1,1's (radix b).
The OP asked what to do when the formula yields a nonreduced result.
You replied: reduce again. He asked if one needs to reduce twice, and
asked what is the max number of reductions required. You replied to
keep reducing until the result is less than the modulus, and asked
him how many times he casts nines from a 206-digit decimal number.
At this point the thread continues as above. The point of my above
quoted reply is simple. By answering a query about casting 91's by
comparing it to casting 9's, you're implicitly assuming that there
is only one way to cast out 9's, and that this is the same way one
casts out 91's. My reply shows that this is false, since one very
efficient way to cast 9's mentally is simply to perform the digit
additions in Z/9 (not in Z), i.e. memorize the Z/9 addition table.
It produces no carries/overflows and requires no modular reduction,
nor iteration. Hence it does not yield a simpler model of casting
where multiple iterations occur. I could say more about how this
produces a much cleaner semantic view of the underlying algebraic
structure (modular reduction), but I have already done that here
many times before [1], and we have beaten this dead horse enough.
--Bill Dubuque
[1] http://google.com/groups/search?q=group:*math*+dubuque+casting
Michael Press
Bill Dubuque <w...@nestle.csail.mit.edu> wrote:
[...]
> You both missed my point. Let's recap. I showed the OP how to compute
> modular reductions (mod x^2-x+1), i.e. cast 91's, or b-1,1's (radix b).
> The OP asked what to do when the formula yields a nonreduced result.
> You replied: reduce again. He asked if one needs to reduce twice, and
> asked what is the max number of reductions required. You replied to
> keep reducing until the result is less than the modulus, and asked
> him how many times he casts nines from a 206-digit decimal number.
>
> At this point the thread continues as above. The point of my above
> quoted reply is simple. By answering a query about casting 91's by
> comparing it to casting 9's, you're implicitly assuming that there
> is only one way to cast out 9's, and that this is the same way one
> casts out 91's. My reply shows that this is false, since one very
> efficient way to cast 9's mentally is simply to perform the digit
> additions in Z/9 (not in Z), i.e. memorize the Z/9 addition table.
> It produces no carries/overflows and requires no modular reduction,
> nor iteration. Hence it does not yield a simpler model of casting
> where multiple iterations occur. I could say more about how this
> produces a much cleaner semantic view of the underlying algebraic
> structure (modular reduction), but I have already done that here
> many times before [1], and we have beaten this dead horse enough.
>
> --Bill Dubuque
>
> [1] http://google.com/groups/search?q=group:*math*+dubuque+casting
Thanks for the summary. We are still answering the question
"How many times will I have to reduce?"
The answer hinges on the ring in which we do
arithmetic, and the reduced residue set. Many stored
program computers do arithmetic in Z/2^32.Z. I dispute
your assertion that most people do mental casting out
nines in Z/9Z. I think most people work in Z and reduce
after most arithmetic operations, therefore reducing
almost as many times as there are decimal digits. In
the example of Z/(x^2-x+1)Z you answer that we can
simplify the reduction algorithm after the initial big
reduction. I agree. But it is still reduction to a
reduced residue set of Z/(x^2-x+1)Z. We are not
actually _calculating_ in Z/(x^2-x+1)Z. I think my
answer stands. We reduce until we have a result in the
reduced residue set.
--
Michael Press