Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c++ > #118058 > unrolled thread
| Started by | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| First post | 2023-12-10 10:46 +0100 |
| Last post | 2024-02-14 15:57 +0100 |
| Articles | 20 on this page of 213 — 14 participants |
Back to article view | Back to comp.lang.c++
Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-10 10:46 +0100
Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2023-12-10 21:48 +0000
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-11 04:15 +0100
Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2023-12-11 17:12 +0000
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-11 18:19 +0100
Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2023-12-13 15:16 +0000
Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2023-12-13 15:25 +0000
Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2023-12-14 15:06 +0000
Re: Sieve of Erastosthenes optimized to the max red floyd <no.spam.here@its.invalid> - 2023-12-14 08:20 -0800
Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2023-12-23 10:30 -0800
Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2023-12-23 21:20 +0000
Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2023-12-24 00:36 -0800
Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2023-12-29 18:03 +0000
Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-01-13 21:31 -0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-20 13:44 +0100
Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2023-12-21 15:30 +0000
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-21 17:07 +0100
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-21 17:13 +0100
Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2023-12-23 10:21 -0800
Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2023-12-23 21:21 +0000
Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2023-12-24 10:49 -0800
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-21 14:23 -0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-22 04:28 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-21 20:02 -0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-22 17:55 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-23 12:52 -0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-24 11:03 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-24 13:24 -0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-26 06:00 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-25 21:39 -0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-26 10:27 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-26 12:24 -0800
Re: Sieve of Erastosthenes optimized to the max Kaz Kylheku <433-929-6894@kylheku.com> - 2023-12-26 23:35 +0000
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-26 15:37 -0800
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-26 21:59 -0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-27 10:23 +0100
Re: Sieve of Erastosthenes optimized to the max Kaz Kylheku <433-929-6894@kylheku.com> - 2023-12-27 20:49 +0000
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-28 12:00 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-28 15:38 -0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-29 04:17 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-28 20:58 -0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-29 10:58 +0100
Re: Sieve of Erastosthenes optimized to the max David Brown <david.brown@hesbynett.no> - 2023-12-29 13:56 +0100
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-29 17:04 +0100
Re: Sieve of Erastosthenes optimized to the max David Brown <david.brown@hesbynett.no> - 2023-12-30 19:27 +0100
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-31 11:22 +0100
Re: Sieve of Erastosthenes optimized to the max scott@slp53.sl.home (Scott Lurndal) - 2023-12-31 18:49 +0000
Re: Sieve of Erastosthenes optimized to the max David Brown <david.brown@hesbynett.no> - 2024-01-01 12:46 +0100
Re: Sieve of Erastosthenes optimized to the max scott@slp53.sl.home (Scott Lurndal) - 2023-12-29 16:01 +0000
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-29 17:06 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-29 13:45 -0800
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-29 14:09 -0800
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-29 14:12 -0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-30 05:42 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-29 20:45 -0800
Re: Sieve of Erastosthenes optimized to the max Kaz Kylheku <433-929-6894@kylheku.com> - 2023-12-30 04:56 +0000
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-30 06:09 +0100
Re: Sieve of Erastosthenes optimized to the max Kaz Kylheku <433-929-6894@kylheku.com> - 2023-12-30 05:51 +0000
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-30 10:15 +0100
Re: Sieve of Erastosthenes optimized to the max Kaz Kylheku <433-929-6894@kylheku.com> - 2023-12-30 20:35 +0000
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-31 06:54 +0100
Re: Sieve of Erastosthenes optimized to the max Kaz Kylheku <433-929-6894@kylheku.com> - 2023-12-31 07:01 +0000
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-31 11:20 +0100
Re: Sieve of Erastosthenes optimized to the max Kaz Kylheku <433-929-6894@kylheku.com> - 2023-12-31 17:30 +0000
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-01-01 06:21 +0100
Re: Sieve of Erastosthenes optimized to the max scott@slp53.sl.home (Scott Lurndal) - 2023-12-31 18:44 +0000
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-01-01 06:22 +0100
Re: Sieve of Erastosthenes optimized to the max Kaz Kylheku <433-929-6894@kylheku.com> - 2024-01-01 08:28 +0000
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-01-01 14:11 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-01-01 15:36 -0800
Re: Sieve of Erastosthenes optimized to the max Kaz Kylheku <433-929-6894@kylheku.com> - 2023-12-30 04:51 +0000
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-30 12:00 -0800
Re: Sieve of Erastosthenes optimized to the max Kaz Kylheku <433-929-6894@kylheku.com> - 2023-12-29 17:29 +0000
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-30 05:45 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-30 11:58 -0800
Re: Sieve of Erastosthenes optimized to the max red floyd <no.spam.here@its.invalid> - 2023-12-30 14:58 -0800
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-31 11:49 -0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-31 06:51 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-31 11:36 -0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-01-01 07:28 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-31 22:53 -0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-01-01 14:11 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-01-01 15:34 -0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-01-02 11:55 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-01-02 10:38 -0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-01-03 06:48 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-01-03 13:32 -0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-01-04 04:37 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-01-05 19:21 -0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-01-06 08:18 +0100
Re: Sieve of Erastosthenes optimized to the max Kaz Kylheku <433-929-6894@kylheku.com> - 2024-01-06 08:31 +0000
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-01-06 10:30 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-01-06 13:15 -0800
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-01-06 13:19 -0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-01-07 10:14 +0100
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-01-07 10:10 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-01-07 12:46 -0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-01-08 06:48 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-01-08 12:18 -0800
Re: Sieve of Erastosthenes optimized to the max red floyd <no.spam.here@its.invalid> - 2024-01-08 17:14 -0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-01-09 07:19 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-01-09 23:33 -0800
Re: Sieve of Erastosthenes optimized to the max Kaz Kylheku <433-929-6894@kylheku.com> - 2024-01-09 02:02 +0000
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-01-09 15:12 +0100
OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) Vir Campestris <vir.campestris@invalid.invalid> - 2024-01-29 21:31 +0000
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-02-16 08:06 -0800
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) Bonita Montero <Bonita.Montero@gmail.com> - 2024-02-16 18:30 +0100
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-02-23 05:51 -0800
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) Bonita Montero <Bonita.Montero@gmail.com> - 2024-02-24 10:45 +0100
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-02-25 00:48 -0800
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) Bonita Montero <Bonita.Montero@gmail.com> - 2024-02-25 15:51 +0100
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-11 10:10 -0700
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) Bonita Montero <Bonita.Montero@gmail.com> - 2024-03-12 10:15 +0100
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) wij <wyniijj5@gmail.com> - 2024-03-14 12:44 +0800
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) Bonita Montero <Bonita.Montero@gmail.com> - 2024-03-14 07:25 +0100
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) wij <wyniijj5@gmail.com> - 2024-03-14 17:20 +0800
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) wij <wyniijj5@gmail.com> - 2024-03-14 17:35 +0800
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) wij <wyniijj5@gmail.com> - 2024-03-14 17:41 +0800
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) Bonita Montero <Bonita.Montero@gmail.com> - 2024-03-14 19:20 +0100
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) wij <wyniijj5@gmail.com> - 2024-03-15 16:30 +0800
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) Bonita Montero <Bonita.Montero@gmail.com> - 2024-03-15 11:21 +0100
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) wij <wyniijj5@gmail.com> - 2024-03-15 19:07 +0800
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) Bonita Montero <Bonita.Montero@gmail.com> - 2024-03-15 12:56 +0100
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) Bonita Montero <Bonita.Montero@gmail.com> - 2024-03-14 19:20 +0100
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-20 08:35 -0700
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) Bonita Montero <Bonita.Montero@gmail.com> - 2024-04-20 18:34 +0200
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) Bonita Montero <Bonita.Montero@gmail.com> - 2024-04-20 18:35 +0200
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-24 12:28 -0700
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) Bonita Montero <Bonita.Montero@gmail.com> - 2024-04-25 06:19 +0200
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-25 14:14 -0700
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-31 11:39 -0800
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-29 13:52 -0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-27 06:06 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-03-22 19:34 -0700
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-03-23 17:54 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-03-23 14:04 -0700
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-03-24 07:30 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-03-24 12:52 -0700
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-03-24 21:00 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-03-24 13:05 -0700
Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-05-16 17:28 +0100
Re: Sieve of Erastosthenes optimized to the max Ben Bacarisse <ben@bsb.me.uk> - 2024-05-16 21:40 +0100
Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-05-21 19:06 -0700
Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-05-30 12:32 +0100
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-05-30 14:17 +0200
Re: Sieve of Erastosthenes optimized to the max Paavo Helde <eesnimi@osa.pri.ee> - 2024-05-30 19:55 +0300
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-05-31 10:17 +0200
Re: Sieve of Erastosthenes optimized to the max Paavo Helde <eesnimi@osa.pri.ee> - 2024-05-31 20:52 +0300
Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-05-30 22:17 -0700
Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-06-01 21:07 +0100
Re: Sieve of Erastosthenes optimized to the max Richard Damon <richard@damon-family.org> - 2024-06-01 20:43 -0400
Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-06-02 03:23 -0700
Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-06-02 19:50 -0700
Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-06-18 20:56 +0100
Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-06-18 17:34 -0700
Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-06-30 21:47 +0100
Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-07-01 23:20 -0700
Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-07-02 21:24 +0100
Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-07-03 11:25 +0100
Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-07-15 06:15 -0700
Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-07-20 07:41 -0700
OT: Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-07-25 12:46 +0100
Re: OT: Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-08-10 07:07 -0700
Re: OT: Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-08-12 15:32 +0100
Re: OT: Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-08-16 07:48 -0700
Re: OT: Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-08-15 17:52 +0100
Re: OT: Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-08-16 08:40 -0700
Re: OT: Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-08-16 19:35 +0200
Re: OT: Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-08-16 19:55 +0200
Re: OT: Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-08-19 21:23 +0100
Re: OT: Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-08-20 17:21 +0200
Re: OT: Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-08-20 17:24 +0200
Re: OT: Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-08-20 17:43 +0200
Re: OT: Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-08-20 17:55 +0100
Re: OT: Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-08-20 18:59 +0200
Re: OT: Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-08-26 12:08 -0700
Re: OT: Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-08-27 06:09 +0200
Re: OT: Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-09-01 21:23 +0100
Re: OT: Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-09-01 20:40 -0700
Re: OT: Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-09-02 07:08 +0200
Re: OT: Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-09-03 17:45 +0100
Re: OT: Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-09-28 03:46 -0700
Re: OT: Re: Sieve of Erastosthenes optimized to the max Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2024-09-28 13:49 -0700
Re: OT: Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-10-02 11:44 +0100
Re: OT: Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-10-02 13:10 +0200
Re: OT: Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-10-07 08:41 -0700
Re: OT: Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-10-20 12:44 +0100
Re: OT: Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-11-04 03:56 -0800
Re: OT: Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-08-19 21:34 +0100
Re: OT: Re: Sieve of Erastosthenes optimized to the max red floyd <no.spam.here@its.invalid> - 2024-08-19 21:08 -0700
Re: OT: Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-08-20 21:14 +0100
Re: OT: Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-08-26 09:35 -0700
Re: OT: Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-08-26 08:31 -0700
Re: OT: Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-08-20 19:20 +0200
Re: OT: Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-08-20 19:36 +0200
Re: OT: Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-08-20 19:39 +0200
Re: OT: Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-08-20 20:13 +0200
Re: OT: Re: Sieve of Erastosthenes optimized to the max scott@slp53.sl.home (Scott Lurndal) - 2024-08-20 20:50 +0000
Re: OT: Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-08-22 17:30 +0100
Re: OT: Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-08-22 18:38 +0200
Re: OT: Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-08-22 21:47 +0100
Re: OT: Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-08-22 21:56 +0100
Re: OT: Re: Sieve of Erastosthenes optimized to the max red floyd <no.spam.here@its.invalid> - 2024-08-22 17:00 -0700
Re: OT: Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-08-26 10:59 -0700
Re: OT: Re: Sieve of Erastosthenes optimized to the max Andrey Tarasevich <andreytarasevich@hotmail.com> - 2024-09-28 15:21 -0700
Re: OT: Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-08-26 12:47 -0700
Re: OT: Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-08-18 19:52 -0700
Re: OT: Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-08-10 17:24 -0700
Re: OT: Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-08-11 00:00 -0700
Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-07-23 07:34 -0700
Re: Sieve of Erastosthenes optimized to the max wij <wyniijj5@gmail.com> - 2024-02-14 00:15 +0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-02-13 19:08 +0100
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-02-14 15:57 +0100
Page 6 of 11 — ← Prev page 1 … 4 5 [6] 7 8 … 11 Next page →
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2024-01-09 07:19 +0100 |
| Message-ID | <unioh9$1tmb9$1@raubtier-asyl.eternal-september.org> |
| In reply to | #118209 |
Am 09.01.2024 um 02:14 schrieb red floyd: > On 1/8/2024 12:18 PM, Chris M. Thomasson wrote: >> On 1/7/2024 9:48 PM, Bonita Montero wrote: >>> Am 07.01.2024 um 21:46 schrieb Chris M. Thomasson: >>> >>>> I know that they had a problem and the provided workaround from >>>> Intel really did help out. ... >>> >>> Absolutely not, not with four way associativity. >>> >> >> Whatever you say; Sigh. I am done with this. > > Intel just needs to call Bonita whenever they have an issue. Intel made a lot of mistakes with Pentium 4 and Itanium. This is rather a minor "mistake".
[toc] | [prev] | [next] | [standalone]
| From | "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> |
|---|---|
| Date | 2024-01-09 23:33 -0800 |
| Message-ID | <unlh8d$2dhg7$1@dont-email.me> |
| In reply to | #118209 |
On 1/8/2024 5:14 PM, red floyd wrote: > On 1/8/2024 12:18 PM, Chris M. Thomasson wrote: >> On 1/7/2024 9:48 PM, Bonita Montero wrote: >>> Am 07.01.2024 um 21:46 schrieb Chris M. Thomasson: >>> >>>> I know that they had a problem and the provided workaround from >>>> Intel really did help out. ... >>> >>> Absolutely not, not with four way associativity. >>> >> >> Whatever you say; Sigh. I am done with this. > > Intel just needs to call Bonita whenever they have an issue. > Okay. You just made me laugh so hard I started to cough a bit! Wow. Cleaned out the pipes, so to speak. Thanks. ROFL! Cough... :^D
[toc] | [prev] | [next] | [standalone]
| From | Kaz Kylheku <433-929-6894@kylheku.com> |
|---|---|
| Date | 2024-01-09 02:02 +0000 |
| Message-ID | <20240108175039.572@kylheku.com> |
| In reply to | #118207 |
On 2024-01-08, Bonita Montero <Bonita.Montero@gmail.com> wrote: > Am 07.01.2024 um 21:46 schrieb Chris M. Thomasson: > >> I know that they had a problem and the provided workaround from Intel >> really did help out. ... > > Absolutely not, not with four way associativity. You are referring to that as if it were some rescuing magic. Four way associativity is quite poor. It's only a step above two-way, which is a step above the bottom of the barrel: direct mapping. The cache entries are tiny on the P4: 32 bytes. An entire set is just 128 bytes. Code that works intensely with a 128 byte block occupies the entire set of four cache blocks. If anything else touches memory that maps to the same set, an evacuation has to take place, and then when that code is resumed, it will take a hit. If two hyperthreads run the same function which works intensively with a 128 byte area of the stack, and the distance between the stacks is a multiple of 8K, they will interfere through the same cache set. The cache set is 128 bytes; each thread wants to keep its own 128 bytes in it. The situation seems far from improbable to me. We don't need more than four hyper-threads in order to blow the four-way set associative cache. We just need more than one in the above scenario. Needing more that four would be the case for threads that are hammering away on a 32 byte block. (And so since there are only two hyperthreads on the P4, that wouldn't be a problem.) -- TXR Programming Language: http://nongnu.org/txr Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal Mastodon: @Kazinator@mstdn.ca NOTE: If you use Google Groups, I don't see you, unless you're whitelisted.
[toc] | [prev] | [next] | [standalone]
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2024-01-09 15:12 +0100 |
| Message-ID | <unjk7k$21eto$1@raubtier-asyl.eternal-september.org> |
| In reply to | #118210 |
Am 09.01.2024 um 03:02 schrieb Kaz Kylheku: > Four way associativity is quite poor. It's only a step above two-way, > which is a step above the bottom of the barrel: direct mapping. That's your opinion. In 2000 this was o.k. > The cache entries are tiny on the P4: 32 bytes. No, the L1 line size is 64 bytes. > An entire set is just 128 bytes. No, four lines each 64 bytes.
[toc] | [prev] | [next] | [standalone]
| From | Vir Campestris <vir.campestris@invalid.invalid> |
|---|---|
| Date | 2024-01-29 21:31 +0000 |
| Subject | OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) |
| Message-ID | <up95f1$kibc$1@dont-email.me> |
| In reply to | #118212 |
I retired last year, and I haven't really written any code since. This has turned out to be quite a fun little thing of a type I haven't had time for for YEARS. And oddly I still don't seem to have enough time for it... It's the garden, and the kid's gardens, and my mum's garden, and all those holidays :) But some optimisations. You'll remember in Bonita's first version the bitmap was initialised to 0xaaaa, because it's a waste of time doing the sieve for 2. I pointed out that we don't need to even store the even numbers. But there's more. If you look at the bitmap when you've sieved for 2 you see 12 34 56 78 11 10 10 10... which is a repeat of 2 after an initialisation word. That's the aaaa. You can do the same with 3 123 456 789 111 110 110 110 except this time the repeat is 3. And annoyingly that doesn't map well down onto a byte-based architecture. You end up with an initial word, then a 3-word repeat. (If your word was 24 or 36 bytes it would only be 1 word, but I haven't seen that since the 1970s) In hex, with lowest byte first, that is fd b6 6d db b6 6d db (That BTW is the same if you only store the odd numbers - a 3-word repeat.) So rather than start off with your bitmap all set to 1s you can set it to this repeating pattern. That replaces all the ANDs for all the values of three with a memory fill with far fewer accesses. You can do the same with 5: 12345 6789a bcdef 11111 11110 11110 11110 You can then AND your pattern for 3 with the one for 5, and get one with a repeat length of 15, and set that into your bitmap. You've now replaced about a fifth of all your AND operations with a flood fill. This can carry on - for a while. Only a short while. You _can_ make a sequence for lots of primes. But it gets quite long, quite quickly. For up to 23, and not storing the evens, it's over 1E8 words long! I was implementing a version of that when something else occurred to me. You can sacrifice speed for store size if you're prepared to do an integer divide for every prime lookup. Group our numbers into 6s like this 012345 6789ab cdefgh (YKWIM) ijklmn Mask out the ones divisible by 2 or 3 and you see 0123-5 -7---b -d---h -i---n Except for the first "page" the pattern is identical. Your algorithm can be: Divide your candidate by 6. If the result is zero look up in the page zero table 0123-5 If it is non-zero index into a translation table like this 010002 If the translation is zero the number is not prime. If it is not zero it is the index of the bit for this page which tells me if the number is prime. And there need only be 2 bits for 6 numbers. (6 is the product of the first primes 2 and 3) It's still worth masking out the even numbers - they don't need the divide, a simple AND detects them - and I suspect it's worth using a much larger number than 6. 3*5*11*13 is 15,015, which seems as though it might be a convenient size. And only about a third of the number aren't known to be primes (5760 to be exact) I might play with that idea some time. But a note for the group of course - optimising this to the max has nothing to do whatever with C++. The only C++ optimising I've found myself doing is using raw pointers, not vector's operator[]. (certainly not the at function). And also I found myself using emplace_back a lot. It's a PITA because you can only emplace back a single item, and it is slow. Andy
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2024-02-16 08:06 -0800 |
| Subject | Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) |
| Message-ID | <86frxsz94r.fsf@linuxsc.com> |
| In reply to | #118262 |
Vir Campestris <vir.campestris@invalid.invalid> writes:
> I retired last year, and I haven't really written any code since. This
> has turned out to be quite a fun little thing of a type I haven't had
> time for for YEARS. And oddly I still don't seem to have enough time
> for it... It's the garden, and the kid's gardens, and my mum's garden,
> and all those holidays :)
>
> But some optimisations. You'll remember in Bonita's first version the
> bitmap was initialised to 0xaaaa, because it's a waste of time doing
> the sieve for 2.
>
> I pointed out that we don't need to even store the even numbers.
>
> But there's more.
>
> If you look at the bitmap when you've sieved for 2 you see
>
> 12 34 56 78
> 11 10 10 10...
> which is a repeat of 2 after an initialisation word. That's the aaaa.
>
> You can do the same with 3
>
> 123 456 789
> 111 110 110 110
>
> except this time the repeat is 3. And annoyingly that doesn't map well
> down onto a byte-based architecture. You end up with an initial word,
> then a 3-word repeat. (If your word was 24 or 36 bytes it would only
> be 1 word, but I haven't seen that since the 1970s)
>
> In hex, with lowest byte first, that is
> fd b6 6d db b6 6d db
>
> (That BTW is the same if you only store the odd numbers - a 3-word repeat.)
>
> So rather than start off with your bitmap all set to 1s you can set it
> to this repeating pattern. That replaces all the ANDs for all the
> values of three with a memory fill with far fewer accesses.
>
> You can do the same with 5:
>
> 12345 6789a bcdef
> 11111 11110 11110 11110
>
> You can then AND your pattern for 3 with the one for 5, and get one
> with a repeat length of 15, and set that into your bitmap. You've now
> replaced about a fifth of all your AND operations with a flood fill.
>
> This can carry on - for a while. Only a short while. You _can_ make a
> sequence for lots of primes. But it gets quite long, quite
> quickly. For up to 23, and not storing the evens, it's over 1E8 words
> long!
>
> I was implementing a version of that when something else occurred to
> me. You can sacrifice speed for store size if you're prepared to do an
> integer divide for every prime lookup.
I explained before how numbers can be considered mod 30, of which
only the residues { 1, 7, 11, 13, 17, 19, 23, 29 } are candidates,
because all other residues are divisible by 2, 3, or 5. And very
conveniently, there are exactly 8 of these residues, so one byte
can be used to represent each block of 30 numbers (only 8 of which
might be prime). That cuts down on the space needed.
I also explained how the divides and remainders can be avoided,
by taking advantage of the structure of how the numbers being
considered are represented, and arranging that the difficult parts
be done at compile time.
I have an implementation (written in C) based on this approach that
determines all primes less than roughly 51.75 billion, taking just
under 56 seconds to complete. (No threading is used - code is all
single threaded.)
> [...]
>
> But a note for the group of course - optimising this to the max has
> nothing to do whatever with C++. The only C++ optimising I've found
> myself doing is using raw pointers, not vector's
> operator[]. (certainly not the at function). And also I found myself
> using emplace_back a lot. It's a PITA because you can only emplace
> back a single item, and it is slow.
My program is written in C and uses ordinary C arrays. I expect it
could be converted to C++ without too much difficulty.
[toc] | [prev] | [next] | [standalone]
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2024-02-16 18:30 +0100 |
| Subject | Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) |
| Message-ID | <uqo64i$3usjj$1@raubtier-asyl.eternal-september.org> |
| In reply to | #118323 |
Am 16.02.2024 um 17:06 schrieb Tim Rentsch: > I have an implementation (written in C) based on this approach that > determines all primes less than roughly 51.75 billion, taking just > under 56 seconds to complete. (No threading is used - code is all > single threaded.) On my 16 core PC this takes 1.73 seconds and 43 seconds overall CPU time without printing the numbers to a file. C:\Users\Boni\Documents\Source\bitmapSieve>timep "x64\Release-clang++\bitmapSieve.exe" 51750000000 "" real 1.729s user 43.094s sys 0.094s cylces 194.738.953.589
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2024-02-23 05:51 -0800 |
| Subject | Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) |
| Message-ID | <86il2fwapd.fsf@linuxsc.com> |
| In reply to | #118324 |
Bonita Montero <Bonita.Montero@gmail.com> writes: > Am 16.02.2024 um 17:06 schrieb Tim Rentsch: > >> I have an implementation (written in C) based on this approach that >> determines all primes less than roughly 51.75 billion, taking just >> under 56 seconds to complete. (No threading is used - code is all >> single threaded.) > > On my 16 core PC this takes 1.73 seconds and 43 seconds > overall CPU time without printing the numbers to a file. > > C:\Users\Boni\Documents\Source\bitmapSieve>timep > "x64\Release-clang++\bitmapSieve.exe" 51750000000 "" > real 1.729s > user 43.094s > sys 0.094s > cylces 194.738.953.589 If you run the program as a single thread, what is the elapsed time? Also how long does the program take to determine all primes up to 3 trillion? Here again I am interested in the single-thread version.
[toc] | [prev] | [next] | [standalone]
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2024-02-24 10:45 +0100 |
| Subject | Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) |
| Message-ID | <urcds6$14fvi$1@raubtier-asyl.eternal-september.org> |
| In reply to | #118331 |
Am 23.02.2024 um 14:51 schrieb Tim Rentsch: > Bonita Montero <Bonita.Montero@gmail.com> writes: > >> Am 16.02.2024 um 17:06 schrieb Tim Rentsch: >> >>> I have an implementation (written in C) based on this approach that >>> determines all primes less than roughly 51.75 billion, taking just >>> under 56 seconds to complete. (No threading is used - code is all >>> single threaded.) >> >> On my 16 core PC this takes 1.73 seconds and 43 seconds >> overall CPU time without printing the numbers to a file. >> >> C:\Users\Boni\Documents\Source\bitmapSieve>timep >> "x64\Release-clang++\bitmapSieve.exe" 51750000000 "" >> real 1.729s >> user 43.094s >> sys 0.094s >> cylces 194.738.953.589 > > If you run the program as a single thread, what is the > elapsed time? C:\Users\Boni\Documents\Source\bitmapSieve>timep "x64\Release-clang++\bitmapSieve.exe" 51750000000 "" 1 real 22.945s user 22.672s sys 0.234s cylces 102.917.207.295 > Also how long does the program take to determine all > primes up to 3 trillion? Here again I am interested > in the single-thread version. C:\Users\Boni\Documents\Source\bitmapSieve>timep "x64\Release-clang++\bitmapSieve.exe" 3000000000 "" 1 real 1.234s user 1.203s sys 0.031s cylces 5.523.677.002
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2024-02-25 00:48 -0800 |
| Subject | Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) |
| Message-ID | <86wmqtszd0.fsf@linuxsc.com> |
| In reply to | #118332 |
Bonita Montero <Bonita.Montero@gmail.com> writes: > Am 23.02.2024 um 14:51 schrieb Tim Rentsch: > >> Bonita Montero <Bonita.Montero@gmail.com> writes: >> >>> Am 16.02.2024 um 17:06 schrieb Tim Rentsch: >>> >>>> I have an implementation (written in C) based on this approach that >>>> determines all primes less than roughly 51.75 billion, taking just >>>> under 56 seconds to complete. (No threading is used - code is all >>>> single threaded.) >>> >>> On my 16 core PC this takes 1.73 seconds and 43 seconds >>> overall CPU time without printing the numbers to a file. >>> >>> C:\Users\Boni\Documents\Source\bitmapSieve>timep >>> "x64\Release-clang++\bitmapSieve.exe" 51750000000 "" >>> real 1.729s >>> user 43.094s >>> sys 0.094s >>> cylces 194.738.953.589 >> >> If you run the program as a single thread, what is the >> elapsed time? > > C:\Users\Boni\Documents\Source\bitmapSieve>timep > "x64\Release-clang++\bitmapSieve.exe" 51750000000 "" 1 > real 22.945s > user 22.672s > sys 0.234s > cylces 102.917.207.295 Hmmm. Interesting that the multi-threaded version uses almost most twice as much CPU as the single-threaded version. I might have guessed more, but not twice as much. >> Also how long does the program take to determine all >> primes up to 3 trillion? Here again I am interested >> in the single-thread version. > > C:\Users\Boni\Documents\Source\bitmapSieve>timep > "x64\Release-clang++\bitmapSieve.exe" 3000000000 "" 1 > real 1.234s > user 1.203s > sys 0.031s > cylces 5.523.677.002 What I asked for was 3 trillion with a T, not 3 billion with a B. Not 3000000000 but 3000000000000.
[toc] | [prev] | [next] | [standalone]
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2024-02-25 15:51 +0100 |
| Subject | Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) |
| Message-ID | <urfk4u$1tar2$1@raubtier-asyl.eternal-september.org> |
| In reply to | #118333 |
Am 25.02.2024 um 09:48 schrieb Tim Rentsch: > Bonita Montero <Bonita.Montero@gmail.com> writes: > >> Am 23.02.2024 um 14:51 schrieb Tim Rentsch: >> >>> Bonita Montero <Bonita.Montero@gmail.com> writes: >>> >>>> Am 16.02.2024 um 17:06 schrieb Tim Rentsch: >>>> >>>>> I have an implementation (written in C) based on this approach that >>>>> determines all primes less than roughly 51.75 billion, taking just >>>>> under 56 seconds to complete. (No threading is used - code is all >>>>> single threaded.) >>>> >>>> On my 16 core PC this takes 1.73 seconds and 43 seconds >>>> overall CPU time without printing the numbers to a file. >>>> >>>> C:\Users\Boni\Documents\Source\bitmapSieve>timep >>>> "x64\Release-clang++\bitmapSieve.exe" 51750000000 "" >>>> real 1.729s >>>> user 43.094s >>>> sys 0.094s >>>> cylces 194.738.953.589 >>> >>> If you run the program as a single thread, what is the >>> elapsed time? >> >> C:\Users\Boni\Documents\Source\bitmapSieve>timep >> "x64\Release-clang++\bitmapSieve.exe" 51750000000 "" 1 >> real 22.945s >> user 22.672s >> sys 0.234s >> cylces 102.917.207.295 > > Hmmm. Interesting that the multi-threaded version uses almost > most twice as much CPU as the single-threaded version. I might > have guessed more, but not twice as much. It's because the threads are competing on the L2-cache. Look at the difference betwen 16 cores without SMT and 16 cores with SMT: C:\Users\Boni\Documents\Source\bitmapSieve>timep "x64\Release-clang++\bitmapSieve.exe" 51750000000 "" 16 real 1.916s user 24.063s sys 0.109s cylces 110.113.013.925 C:\Users\Boni\Documents\Source\bitmapSieve>timep "x64\Release-clang++\bitmapSieve.exe" 51750000000 "" 32 real 1.796s user 44.703s sys 0.063s cylces 203.299.498.170 > >>> Also how long does the program take to determine all >>> primes up to 3 trillion? Here again I am interested >>> in the single-thread version. >> >> C:\Users\Boni\Documents\Source\bitmapSieve>timep >> "x64\Release-clang++\bitmapSieve.exe" 3000000000 "" 1 >> real 1.234s >> user 1.203s >> sys 0.031s >> cylces 5.523.677.002 > > What I asked for was 3 trillion with a T, not 3 billion with > a B. Not 3000000000 but 3000000000000. That would in a bitmap of 375GiB, which won't fit into my memory.
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2024-03-11 10:10 -0700 |
| Subject | Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) |
| Message-ID | <86r0ggr8xb.fsf@linuxsc.com> |
| In reply to | #118334 |
Bonita Montero <Bonita.Montero@gmail.com> writes: > Am 25.02.2024 um 09:48 schrieb Tim Rentsch: > >> Bonita Montero <Bonita.Montero@gmail.com> writes: >> >>> Am 23.02.2024 um 14:51 schrieb Tim Rentsch: >>> >>>> Bonita Montero <Bonita.Montero@gmail.com> writes: >>>> >>>>> Am 16.02.2024 um 17:06 schrieb Tim Rentsch: [...] >>>> Also how long does the program take to determine all >>>> primes up to 3 trillion? Here again I am interested >>>> in the single-thread version. >>> >>> C:\Users\Boni\Documents\Source\bitmapSieve>timep >>> "x64\Release-clang++\bitmapSieve.exe" 3000000000 "" 1 >>> real 1.234s >>> user 1.203s >>> sys 0.031s >>> cylces 5.523.677.002 >> >> What I asked for was 3 trillion with a T, not 3 billion with >> a B. Not 3000000000 but 3000000000000. > > That would in a bitmap of 375GiB, which won't fit into my memory. Sounds like you're using 1 bit per number, most of which are wasted. If you use a different encoding the memory requirements can be much smaller. How much memory do you have on the box? If you have 64G you should be able to determine all primes less than 1.5 trillion, using a simple encoding. I've mentioned this encoding before but let me give it again. If numbers are considered mod 30, there are only 8 residues that are not divisible by 2, 3, or 5. The 8 residues are 1, 7, 11, 13, 17, 19, 23, and 29. So a single byte can hold all the information needed for 30 numbers, which means 1500000000000 / 30 = 50000000000 which is to say 50 gigabytes should suffice.
[toc] | [prev] | [next] | [standalone]
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2024-03-12 10:15 +0100 |
| Subject | Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) |
| Message-ID | <usp6fv$72id$1@raubtier-asyl.eternal-september.org> |
| In reply to | #118506 |
Am 11.03.2024 um 18:10 schrieb Tim Rentsch: > Sounds like you're using 1 bit per number, most of which are > wasted. If you use a different encoding the memory requirements > can be much smaller. How much memory do you have on the box? > If you have 64G you should be able to determine all primes > less than 1.5 trillion, using a simple encoding. I'm omitting even numbers and I handle the number two as a special case; that's the fastest solution. > I've mentioned this encoding before but let me give it again. > If numbers are considered mod 30, there are only 8 residues > that are not divisible by 2, 3, or 5. The 8 residues are > 1, 7, 11, 13, 17, 19, 23, and 29. So a single byte can > hold all the information needed for 30 numbers, which means > > 1500000000000 / 30 = 50000000000 > > which is to say 50 gigabytes should suffice. Show me the code.
[toc] | [prev] | [next] | [standalone]
| From | wij <wyniijj5@gmail.com> |
|---|---|
| Date | 2024-03-14 12:44 +0800 |
| Subject | Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) |
| Message-ID | <b0fef8ad619485b9ce7a821826e84c8de58f15bf.camel@gmail.com> |
| In reply to | #118511 |
On Tue, 2024-03-12 at 10:15 +0100, Bonita Montero wrote:
> Am 11.03.2024 um 18:10 schrieb Tim Rentsch:
>
> > Sounds like you're using 1 bit per number, most of which are
> > wasted. If you use a different encoding the memory requirements
> > can be much smaller. How much memory do you have on the box?
> > If you have 64G you should be able to determine all primes
> > less than 1.5 trillion, using a simple encoding.
>
> I'm omitting even numbers and I handle the number two as a
> special case; that's the fastest solution.
>
> > I've mentioned this encoding before but let me give it again.
> > If numbers are considered mod 30, there are only 8 residues
> > that are not divisible by 2, 3, or 5. The 8 residues are
> > 1, 7, 11, 13, 17, 19, 23, and 29. So a single byte can
> > hold all the information needed for 30 numbers, which means
> >
> > 1500000000000 / 30 = 50000000000
> >
> > which is to say 50 gigabytes should suffice.
>
> Show me the code.
>
Every 30 natural numbers (or more) can be coded in one byte(8 bits):
//----------------------------------------
#include <Wy.stdlib.h>
#include <CSCall/VLInt.h>
// [Syn] PrimeTab is a table for prime numbers
//
class PrimeTab {
public:
typedef uint64_t NumType;
private:
WY_ENSURE(sizeof(NumType)<=sizeof(size_t));
Wy::VLInt m_ptab;
NumType m_maxn;
// [Syn] Get the bit position storing info. for n
// 0= pos for n (n is composite) is not available
//
static size_t bpos(NumType n) {
constexpr NumType Lcm=2*3*5;
const NumType grp= 8*(n/Lcm);
switch(n%30) {
case 1: return grp;
case 7: return grp+1;
case 11: return grp+2;
case 13: return grp+3;
case 17: return grp+4;
case 19: return grp+5;
case 23: return grp+6;
case 29: return grp+7;
default: return 0;
}
};
public:
WY_DECL_REPLY;
PrimeTab() : m_ptab(), m_maxn(0) {};
PrimeTab(const PrimeTab& s) : m_ptab(s.m_ptab), m_maxn(s.m_maxn) {};
PrimeTab(PrimeTab& s, Wy::ByMove_t) : m_ptab(s.m_ptab,Wy::ByMove),
m_maxn(s.m_maxn) {};
explicit PrimeTab(NumType maxn) : m_ptab(), m_maxn(maxn) {
for(NumType n=2; n<=m_maxn; ++n) {
size_t p= bpos(n);
if(p==0) {
continue; // composite number
}
if(m_ptab.bit(p)) {
continue; // composite number
}
for(NumType m=n+n; m<=m_maxn; m+=n) {
Wy::Errno r=m_ptab.set_bit(bpos(m),true);
if(r!=Wy::Ok) {
WY_THROW( Reply(r) );
}
}
};
};
NumType max_num() const { return m_maxn; };
bool is_prime(NumType n) const {
if(n>m_maxn) {
WY_THROW( Reply(EINVAL) );
}
if(n<=6) {
switch(n) {
case 1: // FALLTHROUGH
case 2: // FALLTHROUGH
case 3: // FALLTHROUGH
case 5: return true;
default: return false;
}
}
size_t p= bpos(n);
if(p==0) {
return false;
}
return !m_ptab.bit(p);
};
void swap(PrimeTab& ano) {
m_ptab.swap(ano.m_ptab);
Wy::swap(m_maxn, ano.m_maxn);
};
void reset() {
m_ptab.reset();
};
Wy::Errno reset(NumType maxn) try {
PrimeTab tmp(maxn);
this->swap(tmp);
return Wy::Ok;
}
catch(const Wy::Errno& e) {
WY_RETURN(e);
};
Wy::Errno reset(const PrimeTab& rhs) {
WY_RETURN(m_ptab.reset(rhs.m_ptab));
};
PrimeTab& operator=(const PrimeTab& rhs) {
Wy::Errno r=m_ptab.reset(rhs.m_ptab);
if(r!=Wy::Ok) {
WY_THROW( Reply(r) );
}
return *this;
};
};
[toc] | [prev] | [next] | [standalone]
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2024-03-14 07:25 +0100 |
| Subject | Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) |
| Message-ID | <usu57t$1f3a5$1@raubtier-asyl.eternal-september.org> |
| In reply to | #118515 |
Am 14.03.2024 um 05:44 schrieb wij:
> On Tue, 2024-03-12 at 10:15 +0100, Bonita Montero wrote:
>> Am 11.03.2024 um 18:10 schrieb Tim Rentsch:
>>
>>> Sounds like you're using 1 bit per number, most of which are
>>> wasted. If you use a different encoding the memory requirements
>>> can be much smaller. How much memory do you have on the box?
>>> If you have 64G you should be able to determine all primes
>>> less than 1.5 trillion, using a simple encoding.
>>
>> I'm omitting even numbers and I handle the number two as a
>> special case; that's the fastest solution.
>>
>>> I've mentioned this encoding before but let me give it again.
>>> If numbers are considered mod 30, there are only 8 residues
>>> that are not divisible by 2, 3, or 5. The 8 residues are
>>> 1, 7, 11, 13, 17, 19, 23, and 29. So a single byte can
>>> hold all the information needed for 30 numbers, which means
>>>
>>> 1500000000000 / 30 = 50000000000
>>>
>>> which is to say 50 gigabytes should suffice.
>>
>> Show me the code.
>>
>
> Every 30 natural numbers (or more) can be coded in one byte(8 bits):
Show me a working sieve with that that beats my code.
> //----------------------------------------
> #include <Wy.stdlib.h>
> #include <CSCall/VLInt.h>
>
> // [Syn] PrimeTab is a table for prime numbers
> //
> class PrimeTab {
> public:
> typedef uint64_t NumType;
>
> private:
> WY_ENSURE(sizeof(NumType)<=sizeof(size_t));
> Wy::VLInt m_ptab;
> NumType m_maxn;
>
> // [Syn] Get the bit position storing info. for n
> // 0= pos for n (n is composite) is not available
> //
> static size_t bpos(NumType n) {
> constexpr NumType Lcm=2*3*5;
> const NumType grp= 8*(n/Lcm);
> switch(n%30) {
> case 1: return grp;
> case 7: return grp+1;
> case 11: return grp+2;
> case 13: return grp+3;
> case 17: return grp+4;
> case 19: return grp+5;
> case 23: return grp+6;
> case 29: return grp+7;
> default: return 0;
> }
> };
>
> public:
> WY_DECL_REPLY;
> PrimeTab() : m_ptab(), m_maxn(0) {};
> PrimeTab(const PrimeTab& s) : m_ptab(s.m_ptab), m_maxn(s.m_maxn) {};
> PrimeTab(PrimeTab& s, Wy::ByMove_t) : m_ptab(s.m_ptab,Wy::ByMove),
> m_maxn(s.m_maxn) {};
> explicit PrimeTab(NumType maxn) : m_ptab(), m_maxn(maxn) {
> for(NumType n=2; n<=m_maxn; ++n) {
> size_t p= bpos(n);
> if(p==0) {
> continue; // composite number
> }
> if(m_ptab.bit(p)) {
> continue; // composite number
> }
>
> for(NumType m=n+n; m<=m_maxn; m+=n) {
> Wy::Errno r=m_ptab.set_bit(bpos(m),true);
> if(r!=Wy::Ok) {
> WY_THROW( Reply(r) );
> }
> }
> };
> };
> NumType max_num() const { return m_maxn; };
> bool is_prime(NumType n) const {
> if(n>m_maxn) {
> WY_THROW( Reply(EINVAL) );
> }
> if(n<=6) {
> switch(n) {
> case 1: // FALLTHROUGH
> case 2: // FALLTHROUGH
> case 3: // FALLTHROUGH
> case 5: return true;
> default: return false;
> }
> }
> size_t p= bpos(n);
> if(p==0) {
> return false;
> }
> return !m_ptab.bit(p);
> };
> void swap(PrimeTab& ano) {
> m_ptab.swap(ano.m_ptab);
> Wy::swap(m_maxn, ano.m_maxn);
> };
> void reset() {
> m_ptab.reset();
> };
>
> Wy::Errno reset(NumType maxn) try {
> PrimeTab tmp(maxn);
> this->swap(tmp);
> return Wy::Ok;
> }
> catch(const Wy::Errno& e) {
> WY_RETURN(e);
> };
> Wy::Errno reset(const PrimeTab& rhs) {
> WY_RETURN(m_ptab.reset(rhs.m_ptab));
> };
> PrimeTab& operator=(const PrimeTab& rhs) {
> Wy::Errno r=m_ptab.reset(rhs.m_ptab);
> if(r!=Wy::Ok) {
> WY_THROW( Reply(r) );
> }
> return *this;
> };
> };
>
>
[toc] | [prev] | [next] | [standalone]
| From | wij <wyniijj5@gmail.com> |
|---|---|
| Date | 2024-03-14 17:20 +0800 |
| Subject | Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) |
| Message-ID | <9b017e5354d67cd6f9dbccdb0b43b030b187588c.camel@gmail.com> |
| In reply to | #118516 |
On Thu, 2024-03-14 at 07:25 +0100, Bonita Montero wrote:
> Am 14.03.2024 um 05:44 schrieb wij:
> > On Tue, 2024-03-12 at 10:15 +0100, Bonita Montero wrote:
> > > Am 11.03.2024 um 18:10 schrieb Tim Rentsch:
> > >
> > > > Sounds like you're using 1 bit per number, most of which are
> > > > wasted. If you use a different encoding the memory requirements
> > > > can be much smaller. How much memory do you have on the box?
> > > > If you have 64G you should be able to determine all primes
> > > > less than 1.5 trillion, using a simple encoding.
> > >
> > > I'm omitting even numbers and I handle the number two as a
> > > special case; that's the fastest solution.
> > >
> > > > I've mentioned this encoding before but let me give it again.
> > > > If numbers are considered mod 30, there are only 8 residues
> > > > that are not divisible by 2, 3, or 5. The 8 residues are
> > > > 1, 7, 11, 13, 17, 19, 23, and 29. So a single byte can
> > > > hold all the information needed for 30 numbers, which means
> > > >
> > > > 1500000000000 / 30 = 50000000000
> > > >
> > > > which is to say 50 gigabytes should suffice.
> > >
> > > Show me the code.
> > >
> >
> > Every 30 natural numbers (or more) can be coded in one byte(8 bits):
>
> Show me a working sieve with that that beats my code.
>
I am not "Tim Rentsch". I did not intend to beat your code but try to make
things (what I saw) clear, and thought you might be confused. In general,
I cannot fully understand your code. Last time I copied your code, it did
not compile on my Linux machine.
> > //----------------------------------------
> > #include <Wy.stdlib.h>
> > #include <CSCall/VLInt.h>
> >
> > // [Syn] PrimeTab is a table for prime numbers
> > //
> > class PrimeTab {
> > public:
> > typedef uint64_t NumType;
> >
> > private:
> > WY_ENSURE(sizeof(NumType)<=sizeof(size_t));
> > Wy::VLInt m_ptab;
> > NumType m_maxn;
> >
> > // [Syn] Get the bit position storing info. for n
> > // 0= pos for n (n is composite) is not available
> > //
> > static size_t bpos(NumType n) {
> > constexpr NumType Lcm=2*3*5;
> > const NumType grp= 8*(n/Lcm);
> > switch(n%30) {
> > case 1: return grp;
> > case 7: return grp+1;
> > case 11: return grp+2;
> > case 13: return grp+3;
> > case 17: return grp+4;
> > case 19: return grp+5;
> > case 23: return grp+6;
> > case 29: return grp+7;
> > default: return 0;
> > }
> > };
> >
> > public:
> > WY_DECL_REPLY;
> > PrimeTab() : m_ptab(), m_maxn(0) {};
> > PrimeTab(const PrimeTab& s) : m_ptab(s.m_ptab), m_maxn(s.m_maxn) {};
> > PrimeTab(PrimeTab& s, Wy::ByMove_t) : m_ptab(s.m_ptab,Wy::ByMove),
> > m_maxn(s.m_maxn) {};
> > explicit PrimeTab(NumType maxn) : m_ptab(), m_maxn(maxn) {
> > for(NumType n=2; n<=m_maxn; ++n) {
> > size_t p= bpos(n);
> > if(p==0) {
> > continue; // composite number
> > }
> > if(m_ptab.bit(p)) {
> > continue; // composite number
> > }
> >
> > for(NumType m=n+n; m<=m_maxn; m+=n) {
> > Wy::Errno r=m_ptab.set_bit(bpos(m),true);
> > if(r!=Wy::Ok) {
> > WY_THROW( Reply(r) );
> > }
> > }
> > };
> > };
> > NumType max_num() const { return m_maxn; };
> > bool is_prime(NumType n) const {
> > if(n>m_maxn) {
> > WY_THROW( Reply(EINVAL) );
> > }
> > if(n<=6) {
> > switch(n) {
> > case 1: // FALLTHROUGH
> > case 2: // FALLTHROUGH
> > case 3: // FALLTHROUGH
> > case 5: return true;
> > default: return false;
> > }
> > }
> > size_t p= bpos(n);
> > if(p==0) {
> > return false;
> > }
> > return !m_ptab.bit(p);
> > };
> > void swap(PrimeTab& ano) {
> > m_ptab.swap(ano.m_ptab);
> > Wy::swap(m_maxn, ano.m_maxn);
> > };
> > void reset() {
> > m_ptab.reset();
> > };
> >
> > Wy::Errno reset(NumType maxn) try {
> > PrimeTab tmp(maxn);
> > this->swap(tmp);
> > return Wy::Ok;
> > }
> > catch(const Wy::Errno& e) {
> > WY_RETURN(e);
> > };
> > Wy::Errno reset(const PrimeTab& rhs) {
> > WY_RETURN(m_ptab.reset(rhs.m_ptab));
> > };
> > PrimeTab& operator=(const PrimeTab& rhs) {
> > Wy::Errno r=m_ptab.reset(rhs.m_ptab);
> > if(r!=Wy::Ok) {
> > WY_THROW( Reply(r) );
> > }
> > return *this;
> > };
> > };
> >
> >
>
[toc] | [prev] | [next] | [standalone]
| From | wij <wyniijj5@gmail.com> |
|---|---|
| Date | 2024-03-14 17:35 +0800 |
| Subject | Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) |
| Message-ID | <d8610dd91dce5475873eb9694477d25c1dd2a7ff.camel@gmail.com> |
| In reply to | #118517 |
On Thu, 2024-03-14 at 17:20 +0800, wij wrote:
> On Thu, 2024-03-14 at 07:25 +0100, Bonita Montero wrote:
> > Am 14.03.2024 um 05:44 schrieb wij:
> > > On Tue, 2024-03-12 at 10:15 +0100, Bonita Montero wrote:
> > > > Am 11.03.2024 um 18:10 schrieb Tim Rentsch:
> > > >
> > > > > Sounds like you're using 1 bit per number, most of which are
> > > > > wasted. If you use a different encoding the memory requirements
> > > > > can be much smaller. How much memory do you have on the box?
> > > > > If you have 64G you should be able to determine all primes
> > > > > less than 1.5 trillion, using a simple encoding.
> > > >
> > > > I'm omitting even numbers and I handle the number two as a
> > > > special case; that's the fastest solution.
> > > >
> > > > > I've mentioned this encoding before but let me give it again.
> > > > > If numbers are considered mod 30, there are only 8 residues
> > > > > that are not divisible by 2, 3, or 5. The 8 residues are
> > > > > 1, 7, 11, 13, 17, 19, 23, and 29. So a single byte can
> > > > > hold all the information needed for 30 numbers, which means
> > > > >
> > > > > 1500000000000 / 30 = 50000000000
> > > > >
> > > > > which is to say 50 gigabytes should suffice.
> > > >
> > > > Show me the code.
> > > >
> > >
> > > Every 30 natural numbers (or more) can be coded in one byte(8 bits):
> >
> > Show me a working sieve with that that beats my code.
> >
>
> I am not "Tim Rentsch". I did not intend to beat your code but try to make
> things (what I saw) clear, and thought you might be confused. In general,
> I cannot fully understand your code. Last time I copied your code, it did
> not compile on my Linux machine.
>
> > > //----------------------------------------
> > > #include <Wy.stdlib.h>
> > > #include <CSCall/VLInt.h>
> > >
> > > // [Syn] PrimeTab is a table for prime numbers
> > > //
> > > class PrimeTab {
> > > public:
> > > typedef uint64_t NumType;
> > >
> > > private:
> > > WY_ENSURE(sizeof(NumType)<=sizeof(size_t));
> > > Wy::VLInt m_ptab;
> > > NumType m_maxn;
> > >
> > > // [Syn] Get the bit position storing info. for n
> > > // 0= pos for n (n is composite) is not available
> > > //
> > > static size_t bpos(NumType n) {
> > > constexpr NumType Lcm=2*3*5;
> > > const NumType grp= 8*(n/Lcm);
> > > switch(n%30) {
> > > case 1: return grp;
> > > case 7: return grp+1;
> > > case 11: return grp+2;
> > > case 13: return grp+3;
> > > case 17: return grp+4;
> > > case 19: return grp+5;
> > > case 23: return grp+6;
> > > case 29: return grp+7;
> > > default: return 0;
> > > }
> > > };
> > >
> > > public:
> > > WY_DECL_REPLY;
> > > PrimeTab() : m_ptab(), m_maxn(0) {};
> > > PrimeTab(const PrimeTab& s) : m_ptab(s.m_ptab), m_maxn(s.m_maxn) {};
> > > PrimeTab(PrimeTab& s, Wy::ByMove_t) : m_ptab(s.m_ptab,Wy::ByMove),
> > > m_maxn(s.m_maxn) {};
> > > explicit PrimeTab(NumType maxn) : m_ptab(), m_maxn(maxn) {
> > > for(NumType n=2; n<=m_maxn; ++n) {
> > > size_t p= bpos(n);
> > > if(p==0) {
> > > continue; // composite number
> > > }
> > > if(m_ptab.bit(p)) {
> > > continue; // composite number
> > > }
> > >
> > > for(NumType m=n+n; m<=m_maxn; m+=n) {
> > > Wy::Errno r=m_ptab.set_bit(bpos(m),true);
> > > if(r!=Wy::Ok) {
> > > WY_THROW( Reply(r) );
> > > }
> > > }
> > > };
> > > };
> > > NumType max_num() const { return m_maxn; };
> > > bool is_prime(NumType n) const {
> > > if(n>m_maxn) {
> > > WY_THROW( Reply(EINVAL) );
> > > }
> > > if(n<=6) {
> > > switch(n) {
> > > case 1: // FALLTHROUGH
> > > case 2: // FALLTHROUGH
> > > case 3: // FALLTHROUGH
> > > case 5: return true;
> > > default: return false;
> > > }
> > > }
> > > size_t p= bpos(n);
> > > if(p==0) {
> > > return false;
> > > }
> > > return !m_ptab.bit(p);
> > > };
> > > void swap(PrimeTab& ano) {
> > > m_ptab.swap(ano.m_ptab);
> > > Wy::swap(m_maxn, ano.m_maxn);
> > > };
> > > void reset() {
> > > m_ptab.reset();
> > > };
> > >
> > > Wy::Errno reset(NumType maxn) try {
> > > PrimeTab tmp(maxn);
> > > this->swap(tmp);
> > > return Wy::Ok;
> > > }
> > > catch(const Wy::Errno& e) {
> > > WY_RETURN(e);
> > > };
> > > Wy::Errno reset(const PrimeTab& rhs) {
> > > WY_RETURN(m_ptab.reset(rhs.m_ptab));
> > > };
> > > PrimeTab& operator=(const PrimeTab& rhs) {
> > > Wy::Errno r=m_ptab.reset(rhs.m_ptab);
> > > if(r!=Wy::Ok) {
> > > WY_THROW( Reply(r) );
> > > }
> > > return *this;
> > > };
> > > };
> > >
> > >
> >
>
#include <Wy.stdio.h>
#include "PrimeTab.h"
using namespace Wy;
void t1() {
size_t pcnt;
PrimeTab ptab(1LL<<31);
pcnt=0;
for(size_t n=0; n<ptab.max_num(); ++n) {
if(ptab.is_prime(n)) {
++pcnt;
}
}
cout << "pcnt=" << pcnt << WY_ENDL;
};
int main()
try {
t1();
cout << "OK" WY_ENDL;
return 0;
}
catch(const Errno& e) {
cerr << wrd(e) << WY_ENDL;
return -1;
}
catch(...) {
cerr << "main caught(...)" WY_ENDL;
return -1;
};
//----------------------
[]$ g++ t.cpp -lwy -O2
[]$ time ./a.out
pcnt=105097566
OK
real 0m34.223s
user 0m33.975s
sys 0m0.079s
PrimeTab(1LL<<31) should be able to test number <= 2^32
[toc] | [prev] | [next] | [standalone]
| From | wij <wyniijj5@gmail.com> |
|---|---|
| Date | 2024-03-14 17:41 +0800 |
| Subject | Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) |
| Message-ID | <289d80cf2391f0efbe4f67c6a17647931d4fd184.camel@gmail.com> |
| In reply to | #118518 |
On Thu, 2024-03-14 at 17:35 +0800, wij wrote:
> On Thu, 2024-03-14 at 17:20 +0800, wij wrote:
> > On Thu, 2024-03-14 at 07:25 +0100, Bonita Montero wrote:
> > > Am 14.03.2024 um 05:44 schrieb wij:
> > > > On Tue, 2024-03-12 at 10:15 +0100, Bonita Montero wrote:
> > > > > Am 11.03.2024 um 18:10 schrieb Tim Rentsch:
> > > > >
> > > > > > Sounds like you're using 1 bit per number, most of which are
> > > > > > wasted. If you use a different encoding the memory requirements
> > > > > > can be much smaller. How much memory do you have on the box?
> > > > > > If you have 64G you should be able to determine all primes
> > > > > > less than 1.5 trillion, using a simple encoding.
> > > > >
> > > > > I'm omitting even numbers and I handle the number two as a
> > > > > special case; that's the fastest solution.
> > > > >
> > > > > > I've mentioned this encoding before but let me give it again.
> > > > > > If numbers are considered mod 30, there are only 8 residues
> > > > > > that are not divisible by 2, 3, or 5. The 8 residues are
> > > > > > 1, 7, 11, 13, 17, 19, 23, and 29. So a single byte can
> > > > > > hold all the information needed for 30 numbers, which means
> > > > > >
> > > > > > 1500000000000 / 30 = 50000000000
> > > > > >
> > > > > > which is to say 50 gigabytes should suffice.
> > > > >
> > > > > Show me the code.
> > > > >
> > > >
> > > > Every 30 natural numbers (or more) can be coded in one byte(8 bits):
> > >
> > > Show me a working sieve with that that beats my code.
> > >
> >
> > I am not "Tim Rentsch". I did not intend to beat your code but try to make
> > things (what I saw) clear, and thought you might be confused. In general,
> > I cannot fully understand your code. Last time I copied your code, it did
> > not compile on my Linux machine.
> >
> > > > //----------------------------------------
> > > > #include <Wy.stdlib.h>
> > > > #include <CSCall/VLInt.h>
> > > >
> > > > // [Syn] PrimeTab is a table for prime numbers
> > > > //
> > > > class PrimeTab {
> > > > public:
> > > > typedef uint64_t NumType;
> > > >
> > > > private:
> > > > WY_ENSURE(sizeof(NumType)<=sizeof(size_t));
> > > > Wy::VLInt m_ptab;
> > > > NumType m_maxn;
> > > >
> > > > // [Syn] Get the bit position storing info. for n
> > > > // 0= pos for n (n is composite) is not available
> > > > //
> > > > static size_t bpos(NumType n) {
> > > > constexpr NumType Lcm=2*3*5;
> > > > const NumType grp= 8*(n/Lcm);
> > > > switch(n%30) {
> > > > case 1: return grp;
> > > > case 7: return grp+1;
> > > > case 11: return grp+2;
> > > > case 13: return grp+3;
> > > > case 17: return grp+4;
> > > > case 19: return grp+5;
> > > > case 23: return grp+6;
> > > > case 29: return grp+7;
> > > > default: return 0;
> > > > }
> > > > };
> > > >
> > > > public:
> > > > WY_DECL_REPLY;
> > > > PrimeTab() : m_ptab(), m_maxn(0) {};
> > > > PrimeTab(const PrimeTab& s) : m_ptab(s.m_ptab), m_maxn(s.m_maxn) {};
> > > > PrimeTab(PrimeTab& s, Wy::ByMove_t) : m_ptab(s.m_ptab,Wy::ByMove),
> > > > m_maxn(s.m_maxn) {};
> > > > explicit PrimeTab(NumType maxn) : m_ptab(), m_maxn(maxn) {
> > > > for(NumType n=2; n<=m_maxn; ++n) {
> > > > size_t p= bpos(n);
> > > > if(p==0) {
> > > > continue; // composite number
> > > > }
> > > > if(m_ptab.bit(p)) {
> > > > continue; // composite number
> > > > }
> > > >
> > > > for(NumType m=n+n; m<=m_maxn; m+=n) {
> > > > Wy::Errno r=m_ptab.set_bit(bpos(m),true);
> > > > if(r!=Wy::Ok) {
> > > > WY_THROW( Reply(r) );
> > > > }
> > > > }
> > > > };
> > > > };
> > > > NumType max_num() const { return m_maxn; };
> > > > bool is_prime(NumType n) const {
> > > > if(n>m_maxn) {
> > > > WY_THROW( Reply(EINVAL) );
> > > > }
> > > > if(n<=6) {
> > > > switch(n) {
> > > > case 1: // FALLTHROUGH
> > > > case 2: // FALLTHROUGH
> > > > case 3: // FALLTHROUGH
> > > > case 5: return true;
> > > > default: return false;
> > > > }
> > > > }
> > > > size_t p= bpos(n);
> > > > if(p==0) {
> > > > return false;
> > > > }
> > > > return !m_ptab.bit(p);
> > > > };
> > > > void swap(PrimeTab& ano) {
> > > > m_ptab.swap(ano.m_ptab);
> > > > Wy::swap(m_maxn, ano.m_maxn);
> > > > };
> > > > void reset() {
> > > > m_ptab.reset();
> > > > };
> > > >
> > > > Wy::Errno reset(NumType maxn) try {
> > > > PrimeTab tmp(maxn);
> > > > this->swap(tmp);
> > > > return Wy::Ok;
> > > > }
> > > > catch(const Wy::Errno& e) {
> > > > WY_RETURN(e);
> > > > };
> > > > Wy::Errno reset(const PrimeTab& rhs) {
> > > > WY_RETURN(m_ptab.reset(rhs.m_ptab));
> > > > };
> > > > PrimeTab& operator=(const PrimeTab& rhs) {
> > > > Wy::Errno r=m_ptab.reset(rhs.m_ptab);
> > > > if(r!=Wy::Ok) {
> > > > WY_THROW( Reply(r) );
> > > > }
> > > > return *this;
> > > > };
> > > > };
> > > >
> > > >
> > >
> >
> #include <Wy.stdio.h>
> #include "PrimeTab.h"
>
> using namespace Wy;
>
> void t1() {
> size_t pcnt;
> PrimeTab ptab(1LL<<31);
> pcnt=0;
> for(size_t n=0; n<ptab.max_num(); ++n) {
> if(ptab.is_prime(n)) {
> ++pcnt;
> }
> }
> cout << "pcnt=" << pcnt << WY_ENDL;
> };
>
> int main()
> try {
> t1();
> cout << "OK" WY_ENDL;
> return 0;
> }
> catch(const Errno& e) {
> cerr << wrd(e) << WY_ENDL;
> return -1;
> }
> catch(...) {
> cerr << "main caught(...)" WY_ENDL;
> return -1;
> };
>
> //----------------------
> []$ g++ t.cpp -lwy -O2
> []$ time ./a.out
> pcnt=105097566
> OK
>
> real 0m34.223s
> user 0m33.975s
> sys 0m0.079s
>
> PrimeTab(1LL<<31) should be able to test number <= 2^32
Correction: PrimeTab(1LL<<31) should be able to test number <= 2^62
[toc] | [prev] | [next] | [standalone]
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2024-03-14 19:20 +0100 |
| Subject | Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) |
| Message-ID | <usvf69$1p4qk$2@raubtier-asyl.eternal-september.org> |
| In reply to | #118519 |
Am 14.03.2024 um 10:41 schrieb wij:
> On Thu, 2024-03-14 at 17:35 +0800, wij wrote:
>> On Thu, 2024-03-14 at 17:20 +0800, wij wrote:
>>> On Thu, 2024-03-14 at 07:25 +0100, Bonita Montero wrote:
>>>> Am 14.03.2024 um 05:44 schrieb wij:
>>>>> On Tue, 2024-03-12 at 10:15 +0100, Bonita Montero wrote:
>>>>>> Am 11.03.2024 um 18:10 schrieb Tim Rentsch:
>>>>>>
>>>>>>> Sounds like you're using 1 bit per number, most of which are
>>>>>>> wasted. If you use a different encoding the memory requirements
>>>>>>> can be much smaller. How much memory do you have on the box?
>>>>>>> If you have 64G you should be able to determine all primes
>>>>>>> less than 1.5 trillion, using a simple encoding.
>>>>>>
>>>>>> I'm omitting even numbers and I handle the number two as a
>>>>>> special case; that's the fastest solution.
>>>>>>
>>>>>>> I've mentioned this encoding before but let me give it again.
>>>>>>> If numbers are considered mod 30, there are only 8 residues
>>>>>>> that are not divisible by 2, 3, or 5. The 8 residues are
>>>>>>> 1, 7, 11, 13, 17, 19, 23, and 29. So a single byte can
>>>>>>> hold all the information needed for 30 numbers, which means
>>>>>>>
>>>>>>> 1500000000000 / 30 = 50000000000
>>>>>>>
>>>>>>> which is to say 50 gigabytes should suffice.
>>>>>>
>>>>>> Show me the code.
>>>>>>
>>>>>
>>>>> Every 30 natural numbers (or more) can be coded in one byte(8 bits):
>>>>
>>>> Show me a working sieve with that that beats my code.
>>>>
>>>
>>> I am not "Tim Rentsch". I did not intend to beat your code but try to make
>>> things (what I saw) clear, and thought you might be confused. In general,
>>> I cannot fully understand your code. Last time I copied your code, it did
>>> not compile on my Linux machine.
>>>
>>>>> //----------------------------------------
>>>>> #include <Wy.stdlib.h>
>>>>> #include <CSCall/VLInt.h>
>>>>>
>>>>> // [Syn] PrimeTab is a table for prime numbers
>>>>> //
>>>>> class PrimeTab {
>>>>> public:
>>>>> typedef uint64_t NumType;
>>>>>
>>>>> private:
>>>>> WY_ENSURE(sizeof(NumType)<=sizeof(size_t));
>>>>> Wy::VLInt m_ptab;
>>>>> NumType m_maxn;
>>>>>
>>>>> // [Syn] Get the bit position storing info. for n
>>>>> // 0= pos for n (n is composite) is not available
>>>>> //
>>>>> static size_t bpos(NumType n) {
>>>>> constexpr NumType Lcm=2*3*5;
>>>>> const NumType grp= 8*(n/Lcm);
>>>>> switch(n%30) {
>>>>> case 1: return grp;
>>>>> case 7: return grp+1;
>>>>> case 11: return grp+2;
>>>>> case 13: return grp+3;
>>>>> case 17: return grp+4;
>>>>> case 19: return grp+5;
>>>>> case 23: return grp+6;
>>>>> case 29: return grp+7;
>>>>> default: return 0;
>>>>> }
>>>>> };
>>>>>
>>>>> public:
>>>>> WY_DECL_REPLY;
>>>>> PrimeTab() : m_ptab(), m_maxn(0) {};
>>>>> PrimeTab(const PrimeTab& s) : m_ptab(s.m_ptab), m_maxn(s.m_maxn) {};
>>>>> PrimeTab(PrimeTab& s, Wy::ByMove_t) : m_ptab(s.m_ptab,Wy::ByMove),
>>>>> m_maxn(s.m_maxn) {};
>>>>> explicit PrimeTab(NumType maxn) : m_ptab(), m_maxn(maxn) {
>>>>> for(NumType n=2; n<=m_maxn; ++n) {
>>>>> size_t p= bpos(n);
>>>>> if(p==0) {
>>>>> continue; // composite number
>>>>> }
>>>>> if(m_ptab.bit(p)) {
>>>>> continue; // composite number
>>>>> }
>>>>>
>>>>> for(NumType m=n+n; m<=m_maxn; m+=n) {
>>>>> Wy::Errno r=m_ptab.set_bit(bpos(m),true);
>>>>> if(r!=Wy::Ok) {
>>>>> WY_THROW( Reply(r) );
>>>>> }
>>>>> }
>>>>> };
>>>>> };
>>>>> NumType max_num() const { return m_maxn; };
>>>>> bool is_prime(NumType n) const {
>>>>> if(n>m_maxn) {
>>>>> WY_THROW( Reply(EINVAL) );
>>>>> }
>>>>> if(n<=6) {
>>>>> switch(n) {
>>>>> case 1: // FALLTHROUGH
>>>>> case 2: // FALLTHROUGH
>>>>> case 3: // FALLTHROUGH
>>>>> case 5: return true;
>>>>> default: return false;
>>>>> }
>>>>> }
>>>>> size_t p= bpos(n);
>>>>> if(p==0) {
>>>>> return false;
>>>>> }
>>>>> return !m_ptab.bit(p);
>>>>> };
>>>>> void swap(PrimeTab& ano) {
>>>>> m_ptab.swap(ano.m_ptab);
>>>>> Wy::swap(m_maxn, ano.m_maxn);
>>>>> };
>>>>> void reset() {
>>>>> m_ptab.reset();
>>>>> };
>>>>>
>>>>> Wy::Errno reset(NumType maxn) try {
>>>>> PrimeTab tmp(maxn);
>>>>> this->swap(tmp);
>>>>> return Wy::Ok;
>>>>> }
>>>>> catch(const Wy::Errno& e) {
>>>>> WY_RETURN(e);
>>>>> };
>>>>> Wy::Errno reset(const PrimeTab& rhs) {
>>>>> WY_RETURN(m_ptab.reset(rhs.m_ptab));
>>>>> };
>>>>> PrimeTab& operator=(const PrimeTab& rhs) {
>>>>> Wy::Errno r=m_ptab.reset(rhs.m_ptab);
>>>>> if(r!=Wy::Ok) {
>>>>> WY_THROW( Reply(r) );
>>>>> }
>>>>> return *this;
>>>>> };
>>>>> };
>>>>>
>>>>>
>>>>
>>>
>> #include <Wy.stdio.h>
>> #include "PrimeTab.h"
>>
>> using namespace Wy;
>>
>> void t1() {
>> size_t pcnt;
>> PrimeTab ptab(1LL<<31);
>> pcnt=0;
>> for(size_t n=0; n<ptab.max_num(); ++n) {
>> if(ptab.is_prime(n)) {
>> ++pcnt;
>> }
>> }
>> cout << "pcnt=" << pcnt << WY_ENDL;
>> };
>>
>> int main()
>> try {
>> t1();
>> cout << "OK" WY_ENDL;
>> return 0;
>> }
>> catch(const Errno& e) {
>> cerr << wrd(e) << WY_ENDL;
>> return -1;
>> }
>> catch(...) {
>> cerr << "main caught(...)" WY_ENDL;
>> return -1;
>> };
>>
>> //----------------------
>> []$ g++ t.cpp -lwy -O2
>> []$ time ./a.out
>> pcnt=105097566
>> OK
>>
>> real 0m34.223s
>> user 0m33.975s
>> sys 0m0.079s
>>
>> PrimeTab(1LL<<31) should be able to test number <= 2^32
>
> Correction: PrimeTab(1LL<<31) should be able to test number <= 2^62
You don't have that much memory, even with your compression.
[toc] | [prev] | [next] | [standalone]
| From | wij <wyniijj5@gmail.com> |
|---|---|
| Date | 2024-03-15 16:30 +0800 |
| Subject | Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) |
| Message-ID | <def45cf7211c7cb890cd116df081c7ac1aa04966.camel@gmail.com> |
| In reply to | #118521 |
On Thu, 2024-03-14 at 19:20 +0100, Bonita Montero wrote:
> Am 14.03.2024 um 10:41 schrieb wij:
> > On Thu, 2024-03-14 at 17:35 +0800, wij wrote:
> > > On Thu, 2024-03-14 at 17:20 +0800, wij wrote:
> > > > On Thu, 2024-03-14 at 07:25 +0100, Bonita Montero wrote:
> > > > > Am 14.03.2024 um 05:44 schrieb wij:
> > > > > > On Tue, 2024-03-12 at 10:15 +0100, Bonita Montero wrote:
> > > > > > > Am 11.03.2024 um 18:10 schrieb Tim Rentsch:
> > > > > > >
> > > > > > > > Sounds like you're using 1 bit per number, most of which are
> > > > > > > > wasted. If you use a different encoding the memory requirements
> > > > > > > > can be much smaller. How much memory do you have on the box?
> > > > > > > > If you have 64G you should be able to determine all primes
> > > > > > > > less than 1.5 trillion, using a simple encoding.
> > > > > > >
> > > > > > > I'm omitting even numbers and I handle the number two as a
> > > > > > > special case; that's the fastest solution.
> > > > > > >
> > > > > > > > I've mentioned this encoding before but let me give it again.
> > > > > > > > If numbers are considered mod 30, there are only 8 residues
> > > > > > > > that are not divisible by 2, 3, or 5. The 8 residues are
> > > > > > > > 1, 7, 11, 13, 17, 19, 23, and 29. So a single byte can
> > > > > > > > hold all the information needed for 30 numbers, which means
> > > > > > > >
> > > > > > > > 1500000000000 / 30 = 50000000000
> > > > > > > >
> > > > > > > > which is to say 50 gigabytes should suffice.
> > > > > > >
> > > > > > > Show me the code.
> > > > > > >
> > > > > >
> > > > > > Every 30 natural numbers (or more) can be coded in one byte(8 bits):
> > > > >
> > > > > Show me a working sieve with that that beats my code.
> > > > >
> > > >
> > > > I am not "Tim Rentsch". I did not intend to beat your code but try to make
> > > > things (what I saw) clear, and thought you might be confused. In general,
> > > > I cannot fully understand your code. Last time I copied your code, it did
> > > > not compile on my Linux machine.
> > > >
> > > > > > //----------------------------------------
> > > > > > #include <Wy.stdlib.h>
> > > > > > #include <CSCall/VLInt.h>
> > > > > >
> > > > > > // [Syn] PrimeTab is a table for prime numbers
> > > > > > //
> > > > > > class PrimeTab {
> > > > > > public:
> > > > > > typedef uint64_t NumType;
> > > > > >
> > > > > > private:
> > > > > > WY_ENSURE(sizeof(NumType)<=sizeof(size_t));
> > > > > > Wy::VLInt m_ptab;
> > > > > > NumType m_maxn;
> > > > > >
> > > > > > // [Syn] Get the bit position storing info. for n
> > > > > > // 0= pos for n (n is composite) is not available
> > > > > > //
> > > > > > static size_t bpos(NumType n) {
> > > > > > constexpr NumType Lcm=2*3*5;
> > > > > > const NumType grp= 8*(n/Lcm);
> > > > > > switch(n%30) {
> > > > > > case 1: return grp;
> > > > > > case 7: return grp+1;
> > > > > > case 11: return grp+2;
> > > > > > case 13: return grp+3;
> > > > > > case 17: return grp+4;
> > > > > > case 19: return grp+5;
> > > > > > case 23: return grp+6;
> > > > > > case 29: return grp+7;
> > > > > > default: return 0;
> > > > > > }
> > > > > > };
> > > > > >
> > > > > > public:
> > > > > > WY_DECL_REPLY;
> > > > > > PrimeTab() : m_ptab(), m_maxn(0) {};
> > > > > > PrimeTab(const PrimeTab& s) : m_ptab(s.m_ptab), m_maxn(s.m_maxn) {};
> > > > > > PrimeTab(PrimeTab& s, Wy::ByMove_t) : m_ptab(s.m_ptab,Wy::ByMove),
> > > > > > m_maxn(s.m_maxn) {};
> > > > > > explicit PrimeTab(NumType maxn) : m_ptab(), m_maxn(maxn) {
> > > > > > for(NumType n=2; n<=m_maxn; ++n) {
> > > > > > size_t p= bpos(n);
> > > > > > if(p==0) {
> > > > > > continue; // composite number
> > > > > > }
> > > > > > if(m_ptab.bit(p)) {
> > > > > > continue; // composite number
> > > > > > }
> > > > > >
> > > > > > for(NumType m=n+n; m<=m_maxn; m+=n) {
> > > > > > Wy::Errno r=m_ptab.set_bit(bpos(m),true);
> > > > > > if(r!=Wy::Ok) {
> > > > > > WY_THROW( Reply(r) );
> > > > > > }
> > > > > > }
> > > > > > };
> > > > > > };
> > > > > > NumType max_num() const { return m_maxn; };
> > > > > > bool is_prime(NumType n) const {
> > > > > > if(n>m_maxn) {
> > > > > > WY_THROW( Reply(EINVAL) );
> > > > > > }
> > > > > > if(n<=6) {
> > > > > > switch(n) {
> > > > > > case 1: // FALLTHROUGH
> > > > > > case 2: // FALLTHROUGH
> > > > > > case 3: // FALLTHROUGH
> > > > > > case 5: return true;
> > > > > > default: return false;
> > > > > > }
> > > > > > }
> > > > > > size_t p= bpos(n);
> > > > > > if(p==0) {
> > > > > > return false;
> > > > > > }
> > > > > > return !m_ptab.bit(p);
> > > > > > };
> > > > > > void swap(PrimeTab& ano) {
> > > > > > m_ptab.swap(ano.m_ptab);
> > > > > > Wy::swap(m_maxn, ano.m_maxn);
> > > > > > };
> > > > > > void reset() {
> > > > > > m_ptab.reset();
> > > > > > };
> > > > > >
> > > > > > Wy::Errno reset(NumType maxn) try {
> > > > > > PrimeTab tmp(maxn);
> > > > > > this->swap(tmp);
> > > > > > return Wy::Ok;
> > > > > > }
> > > > > > catch(const Wy::Errno& e) {
> > > > > > WY_RETURN(e);
> > > > > > };
> > > > > > Wy::Errno reset(const PrimeTab& rhs) {
> > > > > > WY_RETURN(m_ptab.reset(rhs.m_ptab));
> > > > > > };
> > > > > > PrimeTab& operator=(const PrimeTab& rhs) {
> > > > > > Wy::Errno r=m_ptab.reset(rhs.m_ptab);
> > > > > > if(r!=Wy::Ok) {
> > > > > > WY_THROW( Reply(r) );
> > > > > > }
> > > > > > return *this;
> > > > > > };
> > > > > > };
> > > > > >
> > > > > >
> > > > >
> > > >
> > > #include <Wy.stdio.h>
> > > #include "PrimeTab.h"
> > >
> > > using namespace Wy;
> > >
> > > void t1() {
> > > size_t pcnt;
> > > PrimeTab ptab(1LL<<31);
> > > pcnt=0;
> > > for(size_t n=0; n<ptab.max_num(); ++n) {
> > > if(ptab.is_prime(n)) {
> > > ++pcnt;
> > > }
> > > }
> > > cout << "pcnt=" << pcnt << WY_ENDL;
> > > };
> > >
> > > int main()
> > > try {
> > > t1();
> > > cout << "OK" WY_ENDL;
> > > return 0;
> > > }
> > > catch(const Errno& e) {
> > > cerr << wrd(e) << WY_ENDL;
> > > return -1;
> > > }
> > > catch(...) {
> > > cerr << "main caught(...)" WY_ENDL;
> > > return -1;
> > > };
> > >
> > > //----------------------
> > > []$ g++ t.cpp -lwy -O2
> > > []$ time ./a.out
> > > pcnt=105097566
> > > OK
> > >
> > > real 0m34.223s
> > > user 0m33.975s
> > > sys 0m0.079s
> > >
> > > PrimeTab(1LL<<31) should be able to test number <= 2^32
> >
> > Correction: PrimeTab(1LL<<31) should be able to test number <= 2^62
>
> You don't have that much memory, even with your compression.
>
//----- factorize.cpp
#include <Wy.stdio.h>
#include <Wy.unistd.h>
#include "PrimeTab.h"
using namespace Wy;
uint64_t read_number() { // Read uint64_t from cin
Errno r;
String buf;
uint64_t res;
cin >> buf;
if((r=strnum(res,buf.c_str()))!=EBADMSG) {
WY_THROW(r);
}
return res;
};
void t1() {
cout << "Setup ptab ... wait (70s on my machine)" WY_ENDL WY_ENDL;
PrimeTab ptab(1LL<<32);
uint64_t num;
for(;;) { // Read number (uint64_t) and print the prime factorization
cout << "Number=";
num= read_number();
cout << num << "= ";
for(uint64_t dvr=2; dvr<=ptab.max_num(); ) {
if(ptab.is_prime(dvr)==false) {
++dvr; continue;
}
if(num%dvr) {
++dvr; continue;
}
cout << dvr << '*';
num/=dvr;
if(num<dvr) {
break;
}
}
if(num>1) {
cout << num;
}
cout << WY_ENDL;
}
};
int main()
try {
t1();
cout << "OK" WY_ENDL;
return 0;
}
catch(const Errno& e) {
cerr << wrd(e) << WY_ENDL;
return -1;
}
catch(...) {
cerr << "main caught(...)" WY_ENDL;
return -1;
};
---------------------------------
[]$ g++ factorize.cpp -lwy -O2
[]$ ./a.out
Setup ptab ... wait (70s on my machine)
Number=18446744073709551615
18446744073709551615= 3*5*17*257*641*65537*6700417*
Number=18446744073709551557
18446744073709551557= 18446744073709551557
Number=
-----------
Note: 18446744073709551615= 2^64-1
Note: 18446744073709551557 is the greatest prime found less than 2^64.
This shoud be the worst case (took about 5 sec.)
Note: Constructing PrimeTab ptab(1LL<<32) consumes about (2^32)/30= 143 (Mbytes)
I know you are addressing hard-ware programming, but IMO, the performance/cost
ratio is very low.
[toc] | [prev] | [next] | [standalone]
Page 6 of 11 — ← Prev page 1 … 4 5 [6] 7 8 … 11 Next page →
Back to top | Article view | comp.lang.c++
csiph-web