[HP35s] Program for prime number (Wheel Sieve and MillerRabin)

04152019, 03:55 PM
(This post was last modified: 04192019 05:46 PM by Albert Chan.)
Post: #55




RE: [HP35s] Program for prime number (Wheel Sieve and MillerRabin)
(04112019 03:18 PM)fred_76 Wrote: Adding brut force to find factors of for "small numbers" If you have built "MR", there is no point doing "brute force". For example, I just created factor.lua, using Pollard's rho Algorithm. My code do 3 deltas for efficiency, but only 1 is really needed. Example, this is from my 7 years old laptop. lua> p = require 'factor' lua> n = 999999998479 lua> n, '=', table.concat(p.factor(n), ' * ')  Lua 5.4 time ~ 1.8 msec 999999998479 = 999961 * 1000039 lua> n = 2^531 lua> n, '=', table.concat(p.factor(n), ' * ')  Lua 5.4 time ~ 0.6 msec 9007199254740991 = 6361 * 69431 * 20394401 Edit: updated factor.lua by replacing MOD n for the delta, and use ABS instead. Speed up ~ 5% Note: Luajit does not work properly with this code. It uses the naive a % b = a  floor(b/a) * a This is my FloorMod patch for Luajit 1.18: https://github.com/LuaJIT/LuaJIT/issues/493 

« Next Oldest  Next Newest »

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