R users, I am having a problem with the modulus operator for large numbers as follows, a <- 2 n <- 561 ## n is the first Carmichael number, so by Fermat's Little Theorem the below should equal zero. (a^(n-1) - 1) %% n [1] 2.193172e+152 ## Seems that R and Fermat disagree ## Also, 1000000000000000000 %% 11 [1] -32 This seems like a bug. Should I be avoiding integer math for large numbers? Thanks, Robert platform i686-pc-linux-gnu arch i686 os linux-gnu system i686, linux-gnu status major 2 minor 0.1 year 2004 month 11 day 15 language R
On Wed, 8 Dec 2004, McGehee, Robert wrote:> R users, I am having a problem with the modulus operator for large > numbers as follows, > > a <- 2 > n <- 561 > ## n is the first Carmichael number, so by Fermat's Little Theorem the > below should equal zero. > > (a^(n-1) - 1) %% n > [1] 2.193172e+152 > ## Seems that R and Fermat disagree > > ## Also, > 1000000000000000000 %% 11 > [1] -32 > > This seems like a bug. Should I be avoiding integer math for large > numbers?You can find out the largest representable integer from .Machine$integer.max, and it is probably 2^31-1. Numbers larger than that are converted to double precision. On the other hand, %% should probably return an error or NaN if .Machine$double.eps times the first operand is greater than 1. -thomas
Hi On Dec 8, 2004, at 04:59 pm, McGehee, Robert wrote:> R users, I am having a problem with the modulus operator for large > numbers as follows, > > a <- 2 > n <- 561 > ## n is the first Carmichael number, so by Fermat's Little Theorem the > below should equal zero. > > (a^(n-1) - 1) %% n > [1] 2.193172e+152 >I don't think Fermat's Little Theorem is relevant here. Euler's theorem would be though: a^phi(561)=1 (mod 561) where phi is the totient function. For your problem, try this: f <- function(a,p){ a <- as.integer(a) p <- as.integer(p) out <- as.integer(1) for(i in 1:p){ out <- (out*a)%%p } return(out) } Then > f(2,561) [1] 1 > f(3,561) [1] 375 (sic) > f(5,561) [1] 1 > best rksh> ## Seems that R and Fermat disagree > > ## Also, > 1000000000000000000 %% 11 > [1] -32 > > Thi______________________________________________ > R-help at stat.math.ethz.ch mailing list > https://stat.ethz.ch/mailman/listinfo/r-help > PLEASE do read the posting guide! > http://www.R-project.org/posting-guide.html > >-- Robin Hankin Uncertainty Analyst Southampton Oceanography Centre European Way, Southampton SO14 3ZH, UK tel 023-8059-7743