modular exponentiation?

[Albert Chan]

Here is a poor man's version, using old luajit 1.18
No 64-bits integer (only 53-bits float), no built-in powmod ...

PHP Code:

function powmod1e10(x,y)            -- x^y % 1e10
    if y == 1 then return x end     -- assumed 0 <= x < 1e10
    local p = math.floor(y/2)
    local t = powmod1e10(x, p)
    local b = t % 1e5               -- last 5 digits
    t = (2*t - b) * b % 1e10        -- t*t % 1e10
    if y == p+p then return t end
    if x <= 9e5 then return t * x % 1e10 end
    b = x % 1e5                     -- odd y, big x
    return ((x-b) * (t%1e5) + b*t) % 1e10
end 


PHP Code:

function modsum(n)                  -- sum(i^i, i=1..n) % 1e10
    local t = 0
    for i = 1,n do t = (t + powmod1e10(i, i)) % 1e10 end
    return t
end 


Some benchmark from my 20 years old Pentium 3:

modsum(1e3) ==> 9110846700 (0.00 seconds)
modsum(1e4) ==> 6237204500 (0.04 seconds)
modsum(1e5) ==> 3031782500 (0.57 seconds)
modsum(1e6) ==> 4077562500 (7.10 seconds)