[erlang-bugs] error in rem operator

[Raimo Niskanen]

My modular math is a bit rusty, but is it not true that 
fact(X) rem 823543 == 0 for all X >= 49, since in
the product fact(49) there are seven 7's making it
divisible with 7 ^ 7 == 823543, and for any X > 49
it still must be divisible with 823543?

I then find that for these X'es in the range [49..1000]
rem 823543 /= 0 (according to Erlang):
[50,51,85,89,90,93,95,96,131,132,133,134,135,136,137,140,141,
 142,143,144,145,146,187,188,190,191,195,228,229,230,231,232,
 234,235,237,238,239,244,277,278,280,282,283,284,285,286,287,
 288,289,290,291,324,326,330,332,333,335,337,374,375,378,379,
 380,383,385,420,421,422,425,426,429,432,433,436,437,470,473,
 474,475,477,480,481,482,483,484,515,516,518,519,521,525,530,
 531,564,566,569,570,573,575,576,578,579,612,613,615,618,621,
 624,625,626,628,660,662,667,669,670,671,672,673,674,709,710,
 713,717,718,719,722,723,760,761,762,763,770,805,808,810,814,
 816,817,818,819,820,854,855,856,857,858,859,860,863,864,865,
 867,868,869,900,902,904,905,908,910,911,912,914,916,917,952,
 953,954,955,956,958,962,964,965,1000]

So the problem starts at fact(50).
1> G = fun (G_, 0) -> 1; (G_, N) -> N * G_(G_, N-1) end.
2> G(G, 0).
3> G(G, 6).
4> L = [{N,G(G, N) rem 823543}  || N <- lists:seq(49, 1000)].
[{49,0},
 {50,823543},
 {51,823543},
 {52,0},
 {53,0},
 {54,0},
 {55,0},
 {56,0},
 {57,0},
 {58,0},
 {59,0},
 {60,0},
 {61,0},
 {62,0},
 {63,0},
 {64,0},
 {65,0},
 {66,0},
 {67,0},
 {68,0},
 {69,0},
 {70,0},
 {71,0},
 {72,0},
 {73,0},
 {74,0},
 {75,0},
 {76,...},
 {...}|...]
5> erlang:display([N||{N,R} <- L, R =/= 0]).
[50,51,85,89,90,93,95,96,131,132,133,134,135,136,137,140,141,
 142,143,144,145,146,187,188,190,191,195,228,229,230,231,232,
 234,235,237,238,239,244,277,278,280,282,283,284,285,286,287,
 288,289,290,291,324,326,330,332,333,335,337,374,375,378,379,
 380,383,385,420,421,422,425,426,429,432,433,436,437,470,473,
 474,475,477,480,481,482,483,484,515,516,518,519,521,525,530,
 531,564,566,569,570,573,575,576,578,579,612,613,615,618,621,
 624,625,626,628,660,662,667,669,670,671,672,673,674,709,710,
 713,717,718,719,722,723,760,761,762,763,770,805,808,810,814,
 816,817,818,819,820,854,855,856,857,858,859,860,863,864,865,
 867,868,869,900,902,904,905,908,910,911,912,914,916,917,952,
 953,954,955,956,958,962,964,965,1000]
true


The question is then: is it a bug in rem or in the bignums?
As you see I used another implementation of fact/1.



On Thu, May 10, 2007 at 04:04:17AM +0000, Jay Anderson wrote:
> I think I may have found a bug. Here's my factorial function:
> 
> /////
> -module(fact).
> -export([fact/1]).
> 
> fact(N) -> fact(N,1).
> fact(0,P) -> P;
> fact(N,P) -> fact(N-1,P*N).
> /////
> 
> Now from the shell I did this:
> 
> c(fact).
> X = fact:fact(1000).
> X rem 823543. %7^7=823543
> 
> This incorrectly gives 823543 instead of 0. Thanks!
> 
> -----Jay
> 
> _______________________________________________
> erlang-bugs mailing list
> erlang-bugs@REDACTED
> http://www.erlang.org/mailman/listinfo/erlang-bugs

-- 

/ Raimo Niskanen, Erlang/OTP, Ericsson AB