[HP35s] Program for prime number (Wheel Sieve and Miller-Rabin)
04-15-2019, 03:55 PM (This post was last modified: 04-19-2019 05:46 PM by Albert Chan.)
Post: #55
 Albert Chan Senior Member Posts: 2,142 Joined: Jul 2018
RE: [HP35s] Program for prime number (Wheel Sieve and Miller-Rabin)
(04-11-2019 03:18 PM)fred_76 Wrote:  Adding brut force to find factors of for "small numbers"

1) I have also merged the "brut force" with the "MR" so that numbers smaller than 20 359 000 will be analysed by brut force, and greater by MR, because MR is slower than brut force for numbers smaller than 20 359 000.

2) When a number is found to be composite, it goes to brut force to find factors. When a factor is found, the quotient is sent back to MR to check if it is composite or prime, and so on. Brut force is however very slow to find factors if they are big. For example it takes only 34s for MR to say 999 999 998 479 is composite, but 2h30 for Brut Force to find its factors...

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^53-1
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 Floor-Mod patch for Luajit 1.18: https://github.com/LuaJIT/LuaJIT/issues/493
 « Next Oldest | Next Newest »

 Messages In This Thread [HP35s] Program for prime number (Wheel Sieve and Miller-Rabin) - fred_76 - 02-11-2019, 05:16 PM RE: Hello and program for prime number (HP35s) - Don Shepherd - 02-12-2019, 12:52 AM RE: [HP35s] Program for prime number (brut force) - Dave Britten - 02-14-2019, 06:48 PM RE: Hello and program for prime number (HP35s) - fred_76 - 02-12-2019, 09:28 AM RE: Hello and program for prime number (HP35s) - Don Shepherd - 02-12-2019, 01:54 PM RE: Hello and program for prime number (HP35s) - fred_76 - 02-12-2019, 06:27 PM RE: Hello and program for prime number (HP35s) - Albert Chan - 02-12-2019, 08:14 PM RE: Hello and program for prime number (HP35s) - fred_76 - 02-13-2019, 10:09 AM RE: [HP35s] Hello and program for prime number - Thomas Klemm - 02-13-2019, 11:53 AM RE: [HP35s] Program for prime number (brut force) - Gerald H - 02-16-2019, 10:45 AM RE: [HP35s] Hello and program for prime number - fred_76 - 02-13-2019, 04:03 PM RE: [HP35s] Hello and program for prime number - fred_76 - 02-13-2019, 04:44 PM RE: [HP35s] Hello and program for prime number - Albert Chan - 02-13-2019, 05:26 PM RE: [HP35s] Hello and program for prime number - Thomas Klemm - 02-13-2019, 07:20 PM RE: [HP35s] Hello and program for prime number - fred_76 - 02-14-2019, 01:10 PM RE: [HP35s] Program for prime number (brut force) - Albert Chan - 02-15-2019, 03:07 PM RE: [HP35s] Program for prime number (brut force) - Albert Chan - 02-14-2019, 06:26 PM RE: [HP35s] Program for prime number (brut force) - fred_76 - 02-14-2019, 07:51 PM RE: [HP35s] Program for prime number (brut force) - Thomas Klemm - 02-14-2019, 08:50 PM RE: [HP35s] Program for prime number (brut force) - fred_76 - 02-15-2019, 08:47 AM RE: [HP35s] Program for prime number (brut force) - Thomas Klemm - 02-14-2019, 09:17 PM RE: [HP35s] Program for prime number (brut force) - Gerald H - 02-16-2019, 11:16 AM RE: [HP35s] Program for prime number (brut force) - Thomas Klemm - 02-16-2019, 11:36 AM RE: [HP35s] Program for prime number (brut force) - fred_76 - 02-16-2019, 11:48 AM RE: [HP35s] Program for prime number (brut force) - Thomas Klemm - 02-16-2019, 11:57 AM RE: [HP35s] Program for prime number (brut force) - Gerald H - 02-16-2019, 12:54 PM RE: [HP35s] Program for prime number (brut force) - fred_76 - 02-16-2019, 02:22 PM RE: [HP35s] Program for prime number (brut force) - Albert Chan - 02-16-2019, 02:29 PM RE: [HP35s] Program for prime number (brut force) - Thomas Klemm - 02-16-2019, 02:12 PM RE: [HP35s] Program for prime number (brut force) - Gerald H - 02-16-2019, 05:39 PM RE: [HP35s] Program for prime number (brut force) - Gerald H - 02-16-2019, 05:43 PM RE: [HP35s] Program for prime number (brut force) - Thomas Klemm - 02-16-2019, 05:57 PM RE: [HP35s] Program for prime number (brut force) - Gerald H - 02-16-2019, 05:59 PM RE: [HP35s] Program for prime number (brut force) - Albert Chan - 02-16-2019, 10:32 PM RE: [HP35s] Program for prime number (brut force) - Thomas Klemm - 02-16-2019, 06:07 PM RE: [HP35s] Program for prime number (brut force) - Gerald H - 02-16-2019, 06:18 PM RE: [HP35s] Program for prime number (brut force) - Gerald H - 02-16-2019, 07:09 PM RE: [HP35s] Program for prime number (brut force) - Albert Chan - 02-16-2019, 07:57 PM RE: [HP35s] Program for prime number (brut force) - Gerald H - 02-17-2019, 05:22 AM RE: [HP35s] Program for prime number (brut force) - Thomas Klemm - 02-16-2019, 08:39 PM RE: [HP35s] Program for prime number (brute force) - Thomas Klemm - 02-17-2019, 04:15 AM RE: [HP35s] Program for prime number (brut force) - Gerald H - 02-17-2019, 05:46 AM RE: [HP35s] Program for prime number (brut force) - Gerald H - 02-17-2019, 04:33 PM RE: [HP35s] Program for prime number (brut force) - Albert Chan - 02-17-2019, 10:58 PM RE: [HP35s] Program for prime number (brut force) - Gerald H - 02-18-2019, 06:09 AM RE: [HP35s] Program for prime number (brut force) - fred_76 - 04-09-2019, 03:52 PM RE: [HP35s] Program for prime number (brut force) - ttw - 04-09-2019, 05:22 PM RE: [HP35s] Program for prime number (brut force) - fred_76 - 04-10-2019, 07:26 AM RE: [HP35s] Program for prime number (brut force) - fred_76 - 04-10-2019, 03:56 PM RE: [HP35s] Program for prime number (brut force) - Albert Chan - 04-11-2019, 02:52 AM RE: [HP35s] Program for prime number (brut force) - ttw - 04-10-2019, 09:24 PM RE: [HP35s] Program for prime number (brut force) - ttw - 04-11-2019, 07:42 AM RE: [HP35s] Program for prime number (brut force) - fred_76 - 04-11-2019, 03:18 PM RE: [HP35s] Program for prime number (Wheel Sieve and Miller-Rabin) - Albert Chan - 04-13-2019, 06:24 PM RE: [HP35s] Program for prime number (Wheel Sieve and Miller-Rabin) - Albert Chan - 04-15-2019 03:55 PM RE: [HP35s] Program for prime number (Wheel Sieve and Miller-Rabin) - Gerald H - 08-22-2022, 10:25 AM

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