modular exponentiation?
10-27-2018, 12:24 AM
Post: #38
 Albert Chan Senior Member Posts: 1,246 Joined: Jul 2018
RE: modular exponentiation?
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) % 1e10end
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 tend

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)
 « Next Oldest | Next Newest »

 Messages In This Thread modular exponentiation? - Bill Duncan - 06-23-2018, 11:49 PM RE: modular exponentiation? - Thomas Klemm - 06-24-2018, 12:21 AM RE: modular exponentiation? - Bill Duncan - 06-24-2018, 03:20 AM RE: modular exponentiation? - Thomas Klemm - 06-24-2018, 12:33 AM RE: modular exponentiation? - Thomas Okken - 06-24-2018, 12:48 AM RE: modular exponentiation? - mfleming - 06-24-2018, 02:46 AM RE: modular exponentiation? - mfleming - 06-24-2018, 02:58 AM RE: modular exponentiation? - Paul Dale - 06-24-2018, 03:42 AM RE: modular exponentiation? - J-F Garnier - 06-24-2018, 08:41 AM RE: modular exponentiation? - Didier Lachieze - 06-24-2018, 09:18 AM RE: modular exponentiation? - John Keith - 06-28-2018, 12:42 AM RE: modular exponentiation? - ijabbott - 06-28-2018, 06:07 PM RE: modular exponentiation? - John Keith - 06-28-2018, 09:40 PM RE: modular exponentiation? - J-F Garnier - 06-24-2018, 11:32 AM RE: modular exponentiation? - Valentin Albillo - 06-24-2018, 09:08 PM RE: modular exponentiation? - sasa - 06-24-2018, 10:21 PM RE: modular exponentiation? - ijabbott - 06-25-2018, 10:09 PM RE: modular exponentiation? - Bill Duncan - 06-25-2018, 10:45 PM RE: modular exponentiation? - brickviking - 06-25-2018, 02:04 AM RE: modular exponentiation? - Thomas Okken - 06-25-2018, 02:44 AM RE: modular exponentiation? - brickviking - 06-25-2018, 10:21 PM RE: modular exponentiation? - Maximilian Hohmann - 06-25-2018, 12:30 PM RE: modular exponentiation? - cyrille de brébisson - 06-25-2018, 06:02 AM RE: modular exponentiation? - Bill Duncan - 06-25-2018, 02:49 PM RE: modular exponentiation? - Thomas Okken - 06-25-2018, 03:43 PM RE: modular exponentiation? - Bill Duncan - 06-25-2018, 04:06 PM RE: modular exponentiation? - Ángel Martin - 10-27-2018, 05:46 AM RE: modular exponentiation? - Thomas Klemm - 06-25-2018, 04:31 PM RE: modular exponentiation? - StephenG1CMZ - 06-25-2018, 05:42 PM RE: modular exponentiation? - Thomas Klemm - 06-28-2018, 09:56 PM RE: modular exponentiation? - John Keith - 06-29-2018, 12:47 AM RE: modular exponentiation? - Bill Duncan - 07-08-2018, 09:50 PM RE: modular exponentiation? - Joe Horn - 07-09-2018, 02:32 AM RE: modular exponentiation? - Thomas Klemm - 07-09-2018, 05:18 AM RE: modular exponentiation? - Gerald H - 07-09-2018, 09:55 AM RE: modular exponentiation? - Thomas Klemm - 07-09-2018, 01:37 PM RE: modular exponentiation? - wynen - 10-26-2018, 06:08 PM RE: modular exponentiation? - rprosperi - 10-26-2018, 07:37 PM RE: modular exponentiation? - Ángel Martin - 10-27-2018, 05:55 AM RE: modular exponentiation? - Albert Chan - 10-27-2018 12:24 AM RE: modular exponentiation? - pier4r - 10-27-2018, 07:28 PM

User(s) browsing this thread: 1 Guest(s)