Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c++ > #118058 > unrolled thread

Sieve of Erastosthenes optimized to the max

Started byBonita Montero <Bonita.Montero@gmail.com>
First post2023-12-10 10:46 +0100
Last post2024-02-14 15:57 +0100
Articles 13 on this page of 213 — 14 participants

Back to article view | Back to comp.lang.c++

Contents

  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 11 of 11 — ← Prev page 1 … 9 10 [11]

#119890 — Re: OT: Re: Sieve of Erastosthenes optimized to the max

FromVir Campestris <vir.campestris@invalid.invalid>
Date2024-08-22 21:47 +0100
SubjectRe: OT: Re: Sieve of Erastosthenes optimized to the max
Message-ID<va884i$ikl3$1@dont-email.me>
In reply to#119882
On 22/08/2024 17:38, Bonita Montero wrote:
> 
> I did "findstr /x "66049" primes.txt" on my output and it didn't
> find that number with 1E10 as its maximum.

Eppur si muove.

I have no idea what is going on here. I even checked that I get the same 
result using clang instead of g++.

Andy

[toc] | [prev] | [next] | [standalone]

#119891 — Re: OT: Re: Sieve of Erastosthenes optimized to the max

FromVir Campestris <vir.campestris@invalid.invalid>
Date2024-08-22 21:56 +0100
SubjectRe: OT: Re: Sieve of Erastosthenes optimized to the max
Message-ID<va88m0$ikl3$2@dont-email.me>
In reply to#119817
On 16/08/2024 18:35, Bonita Montero wrote:
> But basically I don't think it is a good idea to skip numbers exept
> multiples of two. With the three you save a sixth of memory, with
> the five you save a 15-th and at the end you get about 20% less
> storage (1 / (2 * 3) + 1 / (2 * 3 * 5) + 1 / (2 * 3 * 5 * 7) ...)
> for a lot of computation. That's the point where I dropped this
> idea and I think this extra computation is higher than the time
> for the saved memory loads.

I've been running some experiments.

Skipping evens only is nice and simple on computation; that's good.

Skipping something else requires table lookups. I've knocked up some 
code that uses the correct table for skipping primes (but not for mask 
bit selection) and run it for 2*3*5, 2*3*5*7, and 2*3*5*7*11.

Only the last one is faster than just skipping evens. And it's not much 
faster at the price of much more complexity, and a lot more store use.

My hack will only work with a prime which is 1 modulo(2*3*5*7*11) and it 
would take a lot more code to make it work for all the other modulo 
values. And even more if I was to make it work out the bitmaps.

I think we've done this to death now (and still with no C++ content!).

I'm happy with my algorithm:
- Work out a bitmask for some small primes, only as far as is needed to 
get repeats (the repeat length is the product of the primes)
- Work out bitmasks for the next half a dozen. Each of those will have a 
repeat the length of the prime.
- Combine those together into the output bitmap. That requires fewer 
operations than doing each one into the output bitmap
- Process the larger primes. Do the output bitmap in blocks for cache 
friendliness
Note that the larger the prime the less time it takes.

Andy

[toc] | [prev] | [next] | [standalone]

#119892 — Re: OT: Re: Sieve of Erastosthenes optimized to the max

Fromred floyd <no.spam.here@its.invalid>
Date2024-08-22 17:00 -0700
SubjectRe: OT: Re: Sieve of Erastosthenes optimized to the max
Message-ID<va8jfa$k5pk$1@redfloyd.dont-email.me>
In reply to#119891
On 8/22/2024 1:56 PM, Vir Campestris wrote:
> On 16/08/2024 18:35, Bonita Montero wrote:
>> But basically I don't think it is a good idea to skip numbers exept
>> multiples of two. With the three you save a sixth of memory, with
>> the five you save a 15-th and at the end you get about 20% less
>> storage (1 / (2 * 3) + 1 / (2 * 3 * 5) + 1 / (2 * 3 * 5 * 7) ...)
>> for a lot of computation. That's the point where I dropped this
>> idea and I think this extra computation is higher than the time
>> for the saved memory loads.
> 
> I've been running some experiments.
> 
> Skipping evens only is nice and simple on computation; that's good.
> 
> Skipping something else requires table lookups. I've knocked up some 
> code that uses the correct table for skipping primes (but not for mask 
> bit selection) and run it for 2*3*5, 2*3*5*7, and 2*3*5*7*11.
>
You can skip multiples of three, by starting with 7, and then
alternately adding 4 then 2.

e.g.

incr = 2;
for (val = 7 ; val < MAX_PRIME_TO_CHECK ; val += incr)
{
     check_for_prime(val);
     incr = 6 - incr;
}

[toc] | [prev] | [next] | [standalone]

#119913 — Re: OT: Re: Sieve of Erastosthenes optimized to the max

FromTim Rentsch <tr.17687@z991.linuxsc.com>
Date2024-08-26 10:59 -0700
SubjectRe: OT: Re: Sieve of Erastosthenes optimized to the max
Message-ID<86zfoz412y.fsf@linuxsc.com>
In reply to#119892
red floyd <no.spam.here@its.invalid> writes:

> On 8/22/2024 1:56 PM, Vir Campestris wrote:
>
>> On 16/08/2024 18:35, Bonita Montero wrote:
>>
>>> But basically I don't think it is a good idea to skip numbers exept
>>> multiples of two.  With the three you save a sixth of memory, with
>>> the five you save a 15-th and at the end you get about 20% less
>>> storage (1 / (2 * 3) + 1 / (2 * 3 * 5) + 1 / (2 * 3 * 5 * 7) ...)
>>> for a lot of computation.  That's the point where I dropped this
>>> idea and I think this extra computation is higher than the time
>>> for the saved memory loads.
>>
>> I've been running some experiments.
>>
>> Skipping evens only is nice and simple on computation;  that's good.
>>
>> Skipping something else requires table lookups.  I've knocked up some
>> code that uses the correct table for skipping primes (but not for
>> mask bit selection) and run it for 2*3*5, 2*3*5*7, and 2*3*5*7*11.
>
> You can skip multiples of three, by starting with 7, and then
> alternately adding 4 then 2.
>
> e.g.
>
> incr = 2;
> for (val = 7 ; val < MAX_PRIME_TO_CHECK ; val += incr)
> {
>     check_for_prime(val);
>     incr = 6 - incr;
> }

As a matter of style I would normally fold the initialization and
update of 'incr' into the first and third expressions of the for()
loop control.

[toc] | [prev] | [next] | [standalone]

#120440 — Re: OT: Re: Sieve of Erastosthenes optimized to the max

FromAndrey Tarasevich <andreytarasevich@hotmail.com>
Date2024-09-28 15:21 -0700
SubjectRe: OT: Re: Sieve of Erastosthenes optimized to the max
Message-ID<vd9vha$1dva9$1@dont-email.me>
In reply to#119892
On 08/22/24 5:00 PM, red floyd wrote:
> You can skip multiples of three, by starting with 7, and then
> alternately adding 4 then 2.

... by starting with 5 and then alternately adding 2 then 4, if you want 
to be follow the general idea of wheel factorization.

Or by starting with 7 and then adding cyclically { 4, 2, 4, 2, 4, 6, 2, 6 }.

And so forth...

-- 
Best regards,
Andrey

[toc] | [prev] | [next] | [standalone]

#119916 — Re: OT: Re: Sieve of Erastosthenes optimized to the max

FromTim Rentsch <tr.17687@z991.linuxsc.com>
Date2024-08-26 12:47 -0700
SubjectRe: OT: Re: Sieve of Erastosthenes optimized to the max
Message-ID<86r0ab3w2b.fsf@linuxsc.com>
In reply to#119891
Vir Campestris <vir.campestris@invalid.invalid> writes:

> On 16/08/2024 18:35, Bonita Montero wrote:
>
>> But basically I don't think it is a good idea to skip numbers
>> exept multiples of two. [...]
>
> I've been running some experiments.
>
> Skipping evens only is nice and simple on computation;  that's
> good.
>
> Skipping something else requires table lookups.  [...]

It doesn't have to.  One point of the code I've been posting is
that table lookups, including mask productions, are eliminated;
everything gets optimized away so what's left is all compile-time
constants.

> I'm happy with my algorithm:
> - Work out a bitmask for some small primes, only as far as is
> needed to get repeats (the repeat length is the product of the
> primes)
> - Work out bitmasks for the next half a dozen.  Each of those will
> have a repeat the length of the prime.
> - Combine those together into the output bitmap.  That requires
> fewer operations than doing each one into the output bitmap
> - Process the larger primes.  Do the output bitmap in blocks for
> cache friendliness

My experience:

* Special casing primes between 7 and 29 helps (and because it's
  the first step the results can initialize the map);

* Special purpose code where primes are taken in pairs, for the
  set of primes more than 29 and less than 360, with each pair
  being folded into the initialized map, helps (incidentally,
  that is 31 pairs, or 62 primes total);

* The combination of those two steps gives a saving of about 35%;

* Doing striping (the term I use for working in cache-sized
  blocks) seems not to help much, so I don't use striping except
  incidentally in the prime-pairs step;

* Forcing the function for the main second-level loop to be
  inlined saves another 15% or so;

* I haven't tried to measure how the speed-up tricks scale with
  overall number of primes to calculate.  My guess is that they
  are close to linear but I don't have any actual measurements.

[toc] | [prev] | [next] | [standalone]

#119820 — Re: OT: Re: Sieve of Erastosthenes optimized to the max

FromTim Rentsch <tr.17687@z991.linuxsc.com>
Date2024-08-18 19:52 -0700
SubjectRe: OT: Re: Sieve of Erastosthenes optimized to the max
Message-ID<86ttfhcjhr.fsf@linuxsc.com>
In reply to#119816
Tim Rentsch <tr.17687@z991.linuxsc.com> writes:

> Vir Campestris <vir.campestris@invalid.invalid> writes:
>
[...]

>> You seem to have spotted a pattern in the steps that I didn't - I
>> looked at the mask values, and decided it wasn't worth working out
>> which of the 8 possible sequences to use - remembering which was
>> too expensive.  But it's also (I think, I haven't coded it) to work
>> out whether you need to step 2, 4, 8 times the prime.  And that
>> would save more memory.
>
> The possible steps for mod30 are 2 or 4 or 6 times the prime.
>
>> Another thought BTW - whether it's worth storing with a larger
>> modulo - say 2*3*5*7 - not just 2*3*5 is a different decision from
>> deciding whether the steps between primes should take that into
>> consideration.
>
> My guess is that the possible steps are still just 2 or 4 or 6
> (times the prime), but I haven't checked that.

I guessed wrong.  Considered mod 210, there are

   15 steps of  2
   15 steps of  4
   14 steps of  6
    2 steps of  8
    2 steps of 10

(for a total of 48 residues) due to knocking out multiples of 7.

[toc] | [prev] | [next] | [standalone]

#119793 — Re: OT: Re: Sieve of Erastosthenes optimized to the max

FromTim Rentsch <tr.17687@z991.linuxsc.com>
Date2024-08-10 17:24 -0700
SubjectRe: OT: Re: Sieve of Erastosthenes optimized to the max
Message-ID<86ikw7ykh6.fsf@linuxsc.com>
In reply to#119748
Vir Campestris <vir.campestris@invalid.invalid> writes:

This post is my second response to your comments, more
specifically to one part of your comments.

> On 20/07/2024 15:41, Tim Rentsch wrote:
>
>> Vir Campestris <vir.campestris@invalid.invalid> writes:
>>
>>> On 02/07/2024 07:20, Tim Rentsch wrote:

[...]

> I had also considered looking for a mod-div value greater than 30.
>
> Bonita's original code stored a bit for every prime.  We can call
> that a compression ratio of 1.  I store the odd only, so the
> compression ratio is 2.  By storing mod30 you increase that to
> 3.75.  But there's a cost on modern computers because it implies
> lots of byte level access to store.
>
> If on the other hand we store mod(2*3*5*7*11), which is 2310, we
> get 480 candidates.  480 isn't far off 512 which is a nice size
> for us to handle, and gives us an even better compression ratio of
> just over 4.5.  But of course all those tables with 8 or 30
> entries will be getting a bit big and painful.

I tried using a mod 240 encoding, so the units are 64-bit elements,
to see if the more natural sized access would help.  The result ran
slower than the mod 30 code.

The idea of using more primes seems like a natural extension, and
maybe it can work.  Certainly it can get greater compression, which
is a plus.  I had looked before at using a mod 210 encoding (which
is 30 * 7).  My sense is that, unless the extra compression is
essential, the added code complexity will hurt performance more
than it helps.  But I never got to the point of actually coding
it.

[toc] | [prev] | [next] | [standalone]

#119794 — Re: OT: Re: Sieve of Erastosthenes optimized to the max

FromTim Rentsch <tr.17687@z991.linuxsc.com>
Date2024-08-11 00:00 -0700
SubjectRe: OT: Re: Sieve of Erastosthenes optimized to the max
Message-ID<86zfpjsfvh.fsf@linuxsc.com>
In reply to#119748
Vir Campestris <vir.campestris@invalid.invalid> writes:

This posting is my third (and I think last) response to your
last set of comments.

> On 20/07/2024 15:41, Tim Rentsch wrote:
>
>> Vir Campestris <vir.campestris@invalid.invalid> writes:
>>
>>> On 02/07/2024 07:20, Tim Rentsch wrote:
[...]

> What I had considered is an extrapolation from my original code.

About the original code..  One part of it took me a while to
figure out.  I would summarize it as follows.  Rather than
striking all multiples of a given prime before going on to the
next one, you put a limit on the memory of where the strikes
can occur to keep those bytes in the L1 cache.  So several or
many primes are processed at once, as long as the products are
inside the target area (which I think is on the order of half a
megabyte).  I haven't done any careful measurements, but it
does appear as though this approach provides a significant
performance gain.  (I don't have any estimates for how much.)

A cost of using this method is it takes some memory to keep
track of where any non-finished primes are in their multiple
striking.  That cost can be relevant if amount of memory needed
starts to be a significant portion of the L1 cache size.

> For each prime my original code starts with p^2, and sets the bit.
> It than adds p*2, and sets the bit for that.  Since I wasn't
> storing even numbers every prime is odd, which means p^2 is odd.
> p^2+p would be even, so I skip that and go on to p^2+p*2, and so
> on.
>
> Given the mod30 storage I should be able to make a table with 8
> entries, each containing a step and a mask.  The step is the
> number of bytes in the big table to step to for the next bit to
> set;  the mask is the bit to set.
>
> For 37, for example, the first bits we need to set are these:
>
> Mul'ple value   /30     Step    %30
> 37      1369    45              19
> 41      1517    50      5       17
> 47      1739    57      7       29
> 49      1813    60      3       13
> 53      1961    65      5       11
> 59      2183    72      7       23
> 61      2257    75      3       7
> 
> 67      2479    82      7       19
> 71      2627    87      5       17
> 77      2849    94      7       29
> 79      2923    97      3       13
> 83      3071    102     5       11
> 89      3293    109     7       23
> 91      3367    112     3       7
>
>
> You'll see the pattern;  there is a repeat 8 lines long of both
> the Step (which is the delta in the word we need to access) and
> the %30 value.

Right.  There is a regular pattern of deltas, corresponding to
a kind of strength reduction of doing the multiplies.

> So what the code should do is start at p^2, and build this table.
> It'll be different for every prime, and will be quite expensive to
> build.  But once the table is built it can add the step onto the
> current table index, then set the bit corresponding to the %30
> value.  The table should of course contain only the step and the
> bitmask corresponding to the %30 value.

Note that the %30 tables can be shared.  There are 8 of them, one
for each of the eight residues mod 30 of the original prime.

> (I used 37 in this example BTW, because I wanted a value more than
> 30, and with 31 the /30 column increments by 1 each time I added a
> prime)

I get a different result for starting with 31 but that's not
important, I expect one of us made a simple calculation mistake.

If we are looking at a prime p = 30*i + a, then the first
delta for the /30 column is

    (30*i+a) * (30*i+b) / 30 - (30*i+a) * (30*i+a) / 30

which is

     (30*i*i + i*b + i*a + a*b/30) -
     (30*i*i + i*a + i*a + a*a/30)

which is

      i*(b-a) + (a*b/30 - a*a/30)

when we get to 8 elements later, the /30 column is

    (30*i+a) * (30*(i+1)+b) / 30 - (30*i+a) * (30*(i+1)+a) / 30

which is

    (30*i*i + i + i*b + i*a + a + a*b/30)  -
    (30*i*i + i + i*a + i*a + a + a*a/30)

which is again

     i*(b-a) + (a*b/30 - a*a/30)

that is, the same delta as the one eight steps before.  This
formula shows us how to calculate the deltas, with the help of one
table for the (a*b'/30 - a*b/30) values, and one table for the
(b'-b) values, which need to be multiplied by the appropriate i
value (namely, p/30).

So I think the delta calculation can be written

     i*delta_b[x] + delta_bb[x]

where x goes in a circular loop over 8 values [ x0 ... x7 ].

All the above assuming I haven't made an algebraic mistakes, which
certainly is not guaranteed.

Besides showing how to calculate the deltas, the last formula shows
how to reduce the amount of memory needed to save the state of
processing a given prime.  Namely, all that is needed is the
running value of what byte holds the product bit, the index i of
the original prime, and the value for x (three bits) along with
something that shows what range it cycles through (another three
bits).  It should be easy to hold all that state in two 64-bit
words.

If instead we tried to store a table with 8 entries for each prime
that is still being processed, that would use a lot more memory and
eat into our L1 cache memory budget.  At some point we have to
wonder if it would be cheaper to do more recalculation but need
less memory to keep track of where we are.  Not a simple problem.

Forgive me if the above seems a bit scattered.  I started with a
rough roadmap and just dived in and began writing.  Feel free to
ask about anything that isn't clear or doesn't make sense.

[toc] | [prev] | [next] | [standalone]

#119730

FromTim Rentsch <tr.17687@z991.linuxsc.com>
Date2024-07-23 07:34 -0700
Message-ID<86le1s41p5.fsf@linuxsc.com>
In reply to#119603
Vir Campestris <vir.campestris@invalid.invalid> writes:

[...]

I was hoping for some feedback, even if very brief,
before I continue.

[toc] | [prev] | [next] | [standalone]

#118316

Fromwij <wyniijj5@gmail.com>
Date2024-02-14 00:15 +0800
Message-ID<166fa939a9a7a5efc03bf538eb04016de4d932fc.camel@gmail.com>
In reply to#118058
On Sun, 2023-12-10 at 10:46 +0100, Bonita Montero wrote:
> I've parallelized my sieve of Erastosthenes to all cores. The
> parallel
> threads do al the punching of the non-prime multiplex beyond sqrt(
> max
> ). I found that the algorithm is limited by the memory bandwith since
> the bit-range between sqrt( max ) and max is to large to fit inside
> the cache. So I partitioned the each thread to a number of bit-ranges
> that fits inside the L2-cache. With that I got a speedup of factor 28
> when calculating about the first 210 million primes, i.e. all primes
> <= 2 ^ 32.
> On my Zen4 16 core PC under Windows with clang-cl 16.0.5 producing
> the
> primes without any file output is only 0.28s. On my Linux-PC, a Zen2
> 64
> core CPU producing the same number of primes is about 0.09s.
> The file output is done with my own buffering. With that writing the
> mentioned prime number range results in a 2.2GB file which is written
> in about two seconds with a PCIe 4.0 SSD.
> The first parameter is the highest prime candidate to be generated,
> it can be prefixed with 0x for hex values. The second number is the
> name of the output file; it can be "" to suppress file output. The
> third parameter is the number of punching threads; if it is left the
> number of threads defaults to the number of threads reported by the
> runtime.
> 
> #include <iostream>
> #include <cstdlib>
> #include <charconv>
> #include <cstring>
> #include <vector>
> #include <algorithm>
> #include <cmath>
> #include <bit>
> #include <fstream>
> #include <string_view>
> #include <thread>
> #include <mutex>
> #include <condition_variable>
> #include <utility>
> #include <semaphore>
> #include <atomic>
> #include <new>
> #include <span>
> #if defined(_MSC_VER)
> 	#include <intrin.h>
> #elif defined(__GNUC__) || defined(__clang__)
> 	#include <cpuid.h>
> #endif
> 
> #if defined(_MSC_VER)
> 	#pragma warning(disable: 26495)
> #endif
> 
> using namespace std;
> 
> #if defined(__cpp_lib_hardware_interference_size)
> constexpr ptrdiff_t CL_SIZE = hardware_destructive_interference_size;
> #else
> constexpr ptrdiff_t CL_SIZE = 64;
> #endif
> 
> size_t getL2Size();
> 
> int main( int argc, char **argv )
> {
> 	if( argc < 2 )
> 		return EXIT_FAILURE;
> 	auto parse = []( char const *str, bool hex, auto &value )
> 	{
> 		from_chars_result fcr = from_chars( str, str +
> strlen( str ), value, 
> !hex ? 10 : 16 );
> 		return fcr.ec == errc() && !*fcr.ptr;
> 	};
> 	char const *sizeStr = argv[1];
> 	bool hex = sizeStr[0] == '0' && (sizeStr[1] == 'x' ||
> sizeStr[1] == 'X');
> 	sizeStr += 2 * hex;
> 	size_t end;
> 	if( !parse( sizeStr, hex, end ) )
> 		return EXIT_FAILURE;
> 	if( (ptrdiff_t)end++ < 0 )
> 		throw bad_alloc();
> 	unsigned hc;
> 	if( argc < 4 || !parse( argv[3], false, hc ) )
> 		hc = jthread::hardware_concurrency();
> 	if( !hc )
> 		return EXIT_FAILURE;
> 	using word_t = size_t;
> 	constexpr size_t
> 		BITS = sizeof(word_t) * 8,
> 		CL_BITS = CL_SIZE * 8;
> 	union alignas(CL_SIZE) ndi_words_cl { word_t words[CL_SIZE /
> sizeof(word_t)]; ndi_words_cl() {} };
> 	size_t nCls = (end + CL_BITS - 1) / CL_BITS;
> 	vector<ndi_words_cl> sieveCachelines( (end + CL_BITS - 1) /
> CL_BITS );
> 	size_t nWords = (end + BITS - 1) / BITS;
> 	span<word_t> sieve( &sieveCachelines[0].words[0], nWords );
> 	auto fill = sieve.begin();
> 	*fill++ = (word_t)0xAAAAAAAAAAAAAAACu;
> 	if( fill != sieve.end() )
> 		for_each( fill, sieve.end(), []( word_t &w  ) { w = 
> (word_t)0xAAAAAAAAAAAAAAAAu; } );
> 	size_t sqrt = (ptrdiff_t)ceil( ::sqrt( (ptrdiff_t)end ) );
> 	auto punch = [&]( auto, size_t start, size_t end, size_t
> prime )
> 	{
> 		if( start >= end )
> 			return;
> 		size_t multiple = start;
> 		if( prime >= BITS ) [[likely]]
> 			do
> 				sieve[multiple / BITS] &= rotl(
> (word_t)-2, multiple % BITS );
> 			while( (multiple += prime) < end );
> 		else
> 		{
> 			auto pSieve = sieve.begin() + multiple /
> BITS;
> 			do
> 			{
> 				word_t
> 					word = *pSieve,
> 					mask = rotl( (word_t)-2,
> multiple % BITS ),
> 					oldMask;
> 				do
> 					word &= mask,
> 					oldMask = mask,
> 					mask = rotl( mask, prime %
> BITS ),
> 					multiple += prime;
> 				while( mask < oldMask );
> 				*pSieve++ = word;
> 			} while( multiple < end );
> 		}
> 	};
> 	for( size_t prime = 3; prime < sqrt; ++prime )
> 	{
> 		for( auto pSieve = sieve.begin() + prime / BITS; ; )
> 		{
> 			if( word_t w = *pSieve >> prime % BITS; w )
> [[likely]]
> 			{
> 				prime += countr_zero( w );
> 				break;
> 			}
> 			prime = prime + BITS & -(ptrdiff_t)BITS;
> 			if( prime >= sqrt )
> 				break;
> 		}
> 		if( prime >= sqrt ) [[unlikely]]
> 			break;
> 		punch( false_type(), prime * prime, sqrt, prime );
> 	}
> 	auto scan = [&]( size_t start, size_t end, auto fn )
> 	{
> 		for( size_t prime = start; prime < end; )
> 		{
> 			word_t word = sieve[prime / BITS] >> prime %
> BITS;
> 			bool hasBits = word;
> 			for( unsigned gap; word; word >>= gap, word
> >>= 1 )
> 			{
> 				gap = countr_zero( word );
> 				if( (prime += gap) >= end )
> [[unlikely]]
> 					return;
> 				fn( prime );
> 				if( ++prime >= end ) [[unlikely]]
> 					return;
> 			}
> 			prime = (prime + BITS - hasBits) & -
> (ptrdiff_t)BITS;
> 		}
> 	};
> 	size_t bitsPerPartition = (end - sqrt) / hc;
> 	using range_t = pair<size_t, size_t>;
> 	vector<pair<size_t, size_t>> ranges;
> 	ranges.reserve( hc );
> 	for( size_t t = hc, rEnd = end, rStart; t--; rEnd = rStart )
> 	{
> 		rStart = sqrt + t * bitsPerPartition;
> 		size_t rClStart = rStart & -(CL_SIZE * 8);
> 		rStart = rClStart >= sqrt ? rClStart : sqrt;
> 		if( rStart >= rEnd )
> 			continue;
> 		ranges.emplace_back( rStart, rEnd );
> 	}
> 	vector<jthread> threads;
> 	threads.reserve( ranges.size() - 1 );
> 	static auto dbl = []( ptrdiff_t x ) { return (double)x; };
> 	double maxPartitionBits = dbl( getL2Size() ) * 8 / 3;
> 	for( range_t const &range : ranges )
> 	{
> 		auto rangePuncher = [&]( size_t rStart, size_t rEnd
> )
> 		{
> 			double nBits = dbl( rEnd - rStart );
> 			ptrdiff_t nPartitions = (ptrdiff_t)ceil(
> nBits / maxPartitionBits );
> 			double bitsPerPartition = nBits / dbl(
> nPartitions );
> 			for( ptrdiff_t p = nPartitions, pEnd = rEnd,
> pStart; p--; pEnd = pStart )
> 			{
> 				pStart = rStart +
> (ptrdiff_t)((double)p * bitsPerPartition);
> 				pStart &= -(CL_SIZE * 8);
> 				scan( 3, sqrt,
> 					[&]( size_t prime )
> 					{
> 						punch( true_type(),
> (pStart + prime - 1) / prime * prime, pEnd,
> prime );
> 					} );
> 			}
> 		};
> 		if( &range != &ranges.back() )
> 			threads.emplace_back( rangePuncher,
> range.first, range.second );
> 		else
> 			rangePuncher( range.first, range.second );
> 	}
> 	threads.resize( 0 );
> 	if( argc >= 3 && !*argv[2] )
> 		return EXIT_SUCCESS;
> 	ofstream ofs;
> 	ofs.exceptions( ofstream::failbit | ofstream::badbit );
> 	ofs.open( argc >= 3 ? argv[2] : "primes.txt",
> ofstream::binary | 
> ofstream::trunc );
> 	constexpr size_t
> 		BUF_SIZE = 0x100000,
> 		AHEAD = 32;
> 	union ndi_char { char c; ndi_char() {} };
> 	vector<ndi_char> printBuf( BUF_SIZE + AHEAD - 1 );
> 	auto
> 		bufBegin = printBuf.begin(),
> 		bufEnd = bufBegin,
> 		bufFlush = bufBegin + BUF_SIZE;
> 	auto print = [&]() { ofs << string_view( &bufBegin->c,
> &to_address( 
> bufEnd )->c ); };
> 	scan( 2, end,
> 		[&]( size_t prime )
> 		{
> 			auto [ptr, ec] = to_chars( &bufEnd->c,
> &bufEnd[AHEAD - 1].c, prime );
> 			if( ec != errc() ) [[unlikely]]
> 				throw system_error( (int)ec,
> generic_category(), "converson failed" );
> 			bufEnd = ptr - &bufBegin->c + bufBegin; //
> pointer to iterator - NOP
> 			bufEnd++->c = '\n';
> 			if( bufEnd >= bufFlush ) [[unlikely]]
> 				print(), bufEnd = bufBegin;
> 		} );
> 	print();
> }
> 
> size_t getL2Size()
> {
> 	int regs[4];
> 	auto cpuId = [&]( unsigned code )
> 	{
> #if defined(_MSC_VER)
> 		__cpuid( regs, code );
> #elif defined(__GNUC__) || defined(__clang__)
> 		__cpuid(code, regs[0], regs[1], regs[2], regs[3]);
> #endif
> 		return regs[0];
> 	};
> 	if( (unsigned)cpuId( 0x80000000u ) < 0x80000006u )
> 		return 512ull * 1024;
> 	cpuId( 0x80000006u );
> 	return ((unsigned)regs[2] >> 16) * 1024;
> }

I just wrote a class PrimeTab to test prime numbers. It took 73s to
complete.
0.1s is too unbelievable. Something must be wrong.

------------- PrimeTab.h
#include <Wy.stdlib.h>
#include <CSCall/VLInt.h>  // Very Large Integer

// [Syn] PrimeTab is a table for prime numbers
//
class PrimeTab {
    typedef uint64_t NumType;
    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
    //
    size_t bpos(NumType n) {
      switch(n%6) {
        case 1: return 2*(n/6);
        case 5: return  2*(n/6)+1;
        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) {};

    // [Syn] Create prime table for numbers<=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) {
      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);
      Wy::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;
    };
};

-------------- chk_primetab.cpp
#include <Wy.stdio.h>
#include "PrimeTab.h"

using namespace Wy;

void ck1() {
 size_t cnt;
 PrimeTab ptab(1LL<<32);
 cnt=0;
 for(size_t n=0; n<ptab.max_num(); ++n) {
   if(ptab.is_prime(n)) {
     ++cnt;
  //   cout << n << WY_ENDL;
   }
 }
 cout << "cnt=" << cnt << WY_ENDL;
};

int main()
try {
 cout << "Check PrimeTab.h ..." WY_ENDL;
 ck1();
 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++ chk_primetab.cpp -lwy -O2
[]$ time ./a.out
Check PrimeTab.h ...
cnt=203280222
OK

real    1m13.716s
user    1m13.180s
sys     0m0.168s

[toc] | [prev] | [next] | [standalone]

#118317

FromBonita Montero <Bonita.Montero@gmail.com>
Date2024-02-13 19:08 +0100
Message-ID<uqgb64$26mhd$1@raubtier-asyl.eternal-september.org>
In reply to#118316
Am 13.02.2024 um 17:15 schrieb wij:

> I just wrote a class PrimeTab to test prime numbers. It took 73s to
> complete.
> 0.1s is too unbelievable. Something must be wrong.

There's nothing wrong with that. I'm storing the bits as a bitmap and
I'm using a segmented sieve and I partition the part beyond the square
root in chunks which are according to the logical number of CPUs and
these are further divided into chunks which fit into the L2-cache.
And the sequential lookup inside the bitmap below the square root
is done with countl_zero, which maps to a single CPU-instruction
on most computers.
The naive single-threeaded approach without cache-partititioning is
for sure magnitudes slower.

[toc] | [prev] | [next] | [standalone]

#118318

FromBonita Montero <Bonita.Montero@gmail.com>
Date2024-02-14 15:57 +0100
Message-ID<uqikcr$2mghj$1@raubtier-asyl.eternal-september.org>
In reply to#118317
Am 13.02.2024 um 19:08 schrieb Bonita Montero:

> There's nothing wrong with that. ...
Test this version which is the latest where I stopped further development:

#include <iostream>
#include <cstdlib>
#include <charconv>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <bit>
#include <fstream>
#include <string_view>
#include <thread>
#include <utility>
#include <new>
#include <span>
#include <array>
#include <cassert>
#include <sstream>
#if defined(_MSC_VER)
	#include <intrin.h>
#elif defined(__GNUC__) || defined(__clang__)
	#include <cpuid.h>
#endif

#if defined(_MSC_VER)
	#pragma warning(disable: 26495) // uninitialized member
#endif

using namespace std;

#if defined(__cpp_lib_hardware_interference_size)
constexpr ptrdiff_t CL_SIZE = hardware_destructive_interference_size;
#else
constexpr ptrdiff_t CL_SIZE = 64;
#endif

size_t getL2Size();
bool smt();

int main( int argc, char **argv )
{
	try
	{
		if( argc < 2 )
			return EXIT_FAILURE;
		auto parse = []( char const *str, auto &value )
		{
			bool hex = str[0] == '0' && tolower( str[1] ) == 'x';
			str += 2 * hex;
			auto [ptr, ec] = from_chars( str, str + strlen( str ), value, !hex ? 
10 : 16 );
			return ec == errc() && !*ptr;
		};
		size_t end;
		if( !parse( argv[1], end ) )
			return EXIT_FAILURE;
		if( end < 2 )
			return EXIT_FAILURE;
		if( (ptrdiff_t)end++ < 0 )
			throw bad_alloc();
		unsigned
			hc = jthread::hardware_concurrency(),
			nThreads;
		if( argc < 4 || !parse( argv[3], nThreads ) )
			nThreads = hc;
		if( !nThreads )
			return EXIT_FAILURE;
		using word_t = size_t;
		constexpr size_t
			BITS_PER_CL = CL_SIZE * 8,
			BITS = sizeof(word_t) * 8;
		size_t nBits = end / 2;
		union alignas(CL_SIZE) ndi_words_cl { word_t words[CL_SIZE / 
sizeof(word_t)]; ndi_words_cl() {} };
		vector<ndi_words_cl> sieveCachelines( (nBits + BITS_PER_CL - 1) / 
BITS_PER_CL );
		span<word_t> sieve( &sieveCachelines[0].words[0], (nBits + BITS - 1) / 
BITS );
		assert(to_address( sieve.end() ) <= &to_address( sieveCachelines.end() 
)->words[0]);
		fill( sieve.begin(), sieve.end(), -1 );
		auto punch = [&]( size_t start, size_t end, size_t prime, auto )
		{
			size_t
				bit = start / 2,
				bitEnd = end / 2;
			if( bit >= bitEnd )
				return;
			if( prime >= BITS ) [[likely]]
				do [[likely]]
					sieve[bit / BITS] &= rotl( (word_t)-2, bit % BITS );
				while( (bit += prime) < bitEnd );
			else
			{
				auto pSieve = sieve.begin() + bit / BITS;
				do [[likely]]
				{
					word_t
						word = *pSieve,
						mask = rotl( (word_t)-2, bit % BITS ),
						oldMask;
					do
						word &= mask,
						oldMask = mask,
						mask = rotl( mask, prime % BITS ),
						bit += prime;
					while( mask < oldMask );
					*pSieve++ = word;
				} while( bit < bitEnd );
			}
		};
		size_t sqrt = (ptrdiff_t)ceil( ::sqrt( (ptrdiff_t)end ) );
		for( size_t bSqrt = sqrt / 2, bit = 1; bit < bSqrt; ++bit ) [[likely]]
		{
			auto pSieve = sieve.begin() + bit / BITS;
			do [[likely]]
			{
				if( word_t w = *pSieve >> bit % BITS; w ) [[likely]]
				{
					bit += countr_zero( w );
					break;
				}
				++pSieve;
				bit = bit + BITS & -(ptrdiff_t)BITS;
			} while( bit < bSqrt );
			if( bit >= bSqrt ) [[unlikely]]
				break;
			size_t prime = 2 * bit + 1;
			punch( prime * prime, sqrt, prime, false_type() );
		}
		auto scan = [&]( size_t start, size_t end, auto fn )
		{
			size_t
				bit = start / 2,
				bitEnd = end / 2;
			if( bit >= bitEnd )
				return;
			auto pSieve = sieve.begin() + bit / BITS;
			word_t word = *pSieve++ >> bit % BITS;
			for( ; ; )
			{
				size_t nextWordBit = bit + BITS & -(ptrdiff_t)BITS;
				for( unsigned gap; word; word >>= gap, word >>= 1 )
				{
					gap = countr_zero( word );
					bit += gap;
					if( bit >= bitEnd ) [[unlikely]]
						return;
					fn( bit++ * 2 + 1, true_type() );
				}
				bit = nextWordBit;
				if( bit >= bitEnd ) [[unlikely]]
					return;
				word = *pSieve++;
			}
		};
		static auto dbl = []( ptrdiff_t x ) { return (double)x; };
		using range_t = pair<size_t, size_t>;
		vector<range_t> ranges;
		ranges.reserve( nThreads );
		vector<jthread> threads;
		threads.reserve( nThreads );
		auto initiate = [&]( size_t start, auto fn )
		{
			ranges.resize( 0 );
			double threadRange = dbl( end - start ) / nThreads;
			for( size_t t = nThreads, trEnd = end, trStart; t--; trEnd = trStart 
) [[likely]]
			{
				trStart = start + (ptrdiff_t)((ptrdiff_t)t * threadRange + 0.5);
				size_t trClStart = trStart & -(2 * CL_SIZE * 8);
				trStart = trClStart >= start ? trClStart : start;
				if( trStart < trEnd )
					ranges.emplace_back( trStart, trEnd );
			}
			for( range_t const &range : ranges )
				if( &range != &ranges.back() )
					threads.emplace_back( fn, range.first, range.second, true_type() );
				else
					fn( range.first, range.second, false_type() );
			threads.resize( 0 );
		};
		double maxCacheRange = dbl( getL2Size() * 8 * 2 ) / 3 * (smt() && 
nThreads > hc / 2 ? 1 : 2);
		initiate( sqrt,
			[&]( size_t rStart, size_t rEnd, auto )
			{
				double thisThreadRange = dbl( rEnd - rStart );
				ptrdiff_t nCachePartitions = (ptrdiff_t)ceil( thisThreadRange / 
maxCacheRange );
				double cacheRange = thisThreadRange / dbl( nCachePartitions );
				for( size_t p = nCachePartitions, cacheEnd = rEnd, cacheStart; p--; 
cacheEnd = cacheStart ) [[likely]]
				{
					cacheStart = rStart + (ptrdiff_t)((double)(ptrdiff_t)p * cacheRange 
+ 0.5);
					cacheStart &= -(2 * CL_SIZE * 8);
					cacheStart = cacheStart >= sqrt ? cacheStart : sqrt;
					scan( 3, sqrt,
						[&]( size_t prime, auto )
						{
							size_t start = (cacheStart + prime - 1) / prime * prime;
							start = start % 2 ? start : start + prime;
							punch( start, cacheEnd, prime, true_type() );
						} );
				}
			} );
		if( bool count = false; argc >= 3 && (!*argv[2] || (count = strcmp( 
argv[2], "*" ) == 0)) )
		{
			if( !count )
				return EXIT_SUCCESS;
			atomic<size_t> aNPrimes( 1 );
			initiate( 3,
				[&]( size_t rStart, size_t rEnd, auto )
				{
					size_t nPrimes = 0;
					scan( rStart, rEnd, [&]( ... ) { ++nPrimes; } );
					aNPrimes.fetch_add( nPrimes, memory_order::relaxed );
				} );
			cout << aNPrimes.load( memory_order::relaxed ) << " primes" << endl;
			return EXIT_SUCCESS;
		}
		ofstream ofs;
		ofs.exceptions( ofstream::failbit | ofstream::badbit );
		ofs.open( argc >= 3 ? argv[2] : "primes.txt", ofstream::binary | 
ofstream::trunc );
		constexpr size_t
			BUF_SIZE = 0x100000,
			AHEAD = 32;
		union ndi_char { char c; ndi_char() {} };
		vector<ndi_char> rawPrintBuf( BUF_SIZE + AHEAD - 1 );
		span printBuf( &to_address( rawPrintBuf.begin() )->c, &to_address( 
rawPrintBuf.end() )->c );
		auto
			bufBegin = printBuf.begin(),
			bufEnd = bufBegin,
			bufFlush = bufBegin + BUF_SIZE;
		auto print = [&]() { ofs << string_view( bufBegin, bufEnd ); };
		auto printPrime = [&]( size_t prime, auto )
		{
			auto [ptr, ec] = to_chars( &*bufEnd, &bufEnd[AHEAD - 1], prime );
			if( (bool)ec ) [[unlikely]]
				throw system_error( (int)ec, generic_category(), "converson failed" );
			bufEnd = ptr - &*bufBegin + bufBegin; // pointer to iterator - NOP
			*bufEnd++ = '\n';
			if( bufEnd >= bufFlush ) [[unlikely]]
				print(), bufEnd = bufBegin;
		};
		printPrime( 2, false_type() );
		scan( 3, end, printPrime );
		print();
	}
	catch( exception const &exc )
	{
		cout << exc.what() << endl;
	}
}

array<unsigned, 4> cpuId( unsigned code )
{
	array<unsigned, 4> regs;
#if defined(_MSC_VER)
	__cpuid( (int *)&regs[0], code );
#elif defined(__GNUC__) || defined(__clang__)
	__cpuid(code, regs[0], regs[1], regs[2], regs[3]);
#endif
	return regs;
}

bool smt()
{
	if( cpuId( 0 )[0] < 1 )
		return false;
	return cpuId( 1 )[3] >> 28 & 1;
}

size_t getL2Size()
{
	if( cpuId( 0x80000000u )[0] < 0x80000006u )
		return 512ull * 1024;
	return (cpuId( 0x80000006u )[2] >> 16) * 1024;
}

[toc] | [prev] | [standalone]

Page 11 of 11 — ← Prev page 1 … 9 10 [11]

Back to top | Article view | comp.lang.c++

csiph-web