Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #164141 > unrolled thread
| Started by | Mateusz Viste <mateusz@xyz.invalid> |
|---|---|
| First post | 2021-12-31 11:02 +0100 |
| Last post | 2022-01-04 14:21 -0800 |
| Articles | 20 on this page of 180 — 23 participants |
Back to article view | Back to comp.lang.c
How to avoid an overflow during multiplication? Mateusz Viste <mateusz@xyz.invalid> - 2021-12-31 11:02 +0100
Re: How to avoid an overflow during multiplication? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-12-31 12:33 +0000
Re: How to avoid an overflow during multiplication? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-12-31 12:33 +0000
Re: How to avoid an overflow during multiplication? Mateusz Viste <mateusz@xyz.invalid> - 2021-12-31 14:24 +0100
Re: How to avoid an overflow during multiplication? Mateusz Viste <mateusz@xyz.invalid> - 2021-12-31 15:00 +0100
Re: How to avoid an overflow during multiplication? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2021-12-31 11:38 -0800
Re: How to avoid an overflow during multiplication? Mateusz Viste <mateusz@xyz.invalid> - 2021-12-31 20:49 +0100
Re: How to avoid an overflow during multiplication? James Kuyper <jameskuyper@alumni.caltech.edu> - 2021-12-31 18:37 -0500
Re: How to avoid an overflow during multiplication? Mateusz Viste <mateusz@xyz.invalid> - 2022-01-01 17:48 +0100
Re: How to avoid an overflow during multiplication? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-01-21 05:51 -0800
Re: How to avoid an overflow during multiplication? Mateusz Viste <mateusz@xyz.invalid> - 2022-01-21 15:59 +0100
Re: How to avoid an overflow during multiplication? David Brown <david.brown@hesbynett.no> - 2022-01-21 16:19 +0100
Re: How to avoid an overflow during multiplication? Mateusz Viste <mateusz@xyz.invalid> - 2022-01-21 16:51 +0100
Re: How to avoid an overflow during multiplication? James Kuyper <jameskuyper@alumni.caltech.edu> - 2022-01-21 12:08 -0500
Re: How to avoid an overflow during multiplication? David Brown <david.brown@hesbynett.no> - 2022-01-21 18:14 +0100
Re: How to avoid an overflow during multiplication? Mateusz Viste <mateusz@xyz.invalid> - 2022-01-21 18:25 +0100
Re: How to avoid an overflow during multiplication? David Brown <david.brown@hesbynett.no> - 2022-01-21 20:53 +0100
Re: How to avoid an overflow during multiplication? Mateusz Viste <mateusz@xyz.invalid> - 2022-01-21 22:22 +0100
Re: How to avoid an overflow during multiplication? David Brown <david.brown@hesbynett.no> - 2022-01-22 13:05 +0100
Re: How to avoid an overflow during multiplication? Mateusz Viste <mateusz@xyz.invalid> - 2022-01-22 13:53 +0100
Re: How to avoid an overflow during multiplication? Richard Damon <Richard@Damon-Family.org> - 2022-01-22 08:31 -0500
Re: How to avoid an overflow during multiplication? Mateusz Viste <mateusz@xyz.invalid> - 2022-01-22 15:53 +0100
Re: How to avoid an overflow during multiplication? David Brown <david.brown@hesbynett.no> - 2022-01-22 16:46 +0100
Re: How to avoid an overflow during multiplication? Mateusz Viste <mateusz@xyz.invalid> - 2022-01-24 09:33 +0100
Re: How to avoid an overflow during multiplication? David Brown <david.brown@hesbynett.no> - 2022-01-24 10:15 +0100
Re: How to avoid an overflow during multiplication? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-01-22 10:03 -0800
Re: How to avoid an overflow during multiplication? David Brown <david.brown@hesbynett.no> - 2022-01-23 12:28 +0100
Re: How to avoid an overflow during multiplication? Bart <bc@freeuk.com> - 2022-01-23 11:48 +0000
Re: How to avoid an overflow during multiplication? Öö Tiib <ootiib@hot.ee> - 2022-01-23 08:36 -0800
Re: How to avoid an overflow during multiplication? Bart <bc@freeuk.com> - 2022-01-23 16:55 +0000
Re: How to avoid an overflow during multiplication? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-01-23 19:17 -0800
Re: How to avoid an overflow during multiplication? James Kuyper <jameskuyper@alumni.caltech.edu> - 2022-01-21 12:11 -0500
Re: How to avoid an overflow during multiplication? Mateusz Viste <mateusz@xyz.invalid> - 2022-01-21 18:28 +0100
Re: How to avoid an overflow during multiplication? James Kuyper <jameskuyper@alumni.caltech.edu> - 2022-01-21 12:59 -0500
Re: How to avoid an overflow during multiplication? scott@slp53.sl.home (Scott Lurndal) - 2022-01-21 17:23 +0000
Re: How to avoid an overflow during multiplication? Mateusz Viste <mateusz@xyz.invalid> - 2022-01-21 18:35 +0100
Re: How to avoid an overflow during multiplication? scott@slp53.sl.home (Scott Lurndal) - 2022-01-21 18:06 +0000
Re: How to avoid an overflow during multiplication? Mateusz Viste <mateusz@xyz.invalid> - 2022-01-21 20:04 +0100
Re: How to avoid an overflow during multiplication? scott@slp53.sl.home (Scott Lurndal) - 2022-01-21 19:14 +0000
Re: How to avoid an overflow during multiplication? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-01-21 17:02 -0800
Re: How to avoid an overflow during multiplication? scott@slp53.sl.home (Scott Lurndal) - 2022-01-22 16:59 +0000
Re: How to avoid an overflow during multiplication? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-01-24 08:01 -0800
Re: How to avoid an overflow during multiplication? scott@slp53.sl.home (Scott Lurndal) - 2022-01-24 16:24 +0000
Re: How to avoid an overflow during multiplication? scott@slp53.sl.home (Scott Lurndal) - 2022-01-24 17:38 +0000
Re: How to avoid an overflow during multiplication? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-01-24 11:28 -0800
Re: How to avoid an overflow during multiplication? scott@slp53.sl.home (Scott Lurndal) - 2022-01-24 22:44 +0000
Re: How to avoid an overflow during multiplication? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2022-01-24 15:34 -0800
Re: How to avoid an overflow during multiplication? scott@slp53.sl.home (Scott Lurndal) - 2022-01-25 14:50 +0000
Re: How to avoid an overflow during multiplication? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-01-25 18:30 +0000
Re: How to avoid an overflow during multiplication? scott@slp53.sl.home (Scott Lurndal) - 2022-01-25 18:50 +0000
Re: How to avoid an overflow during multiplication? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2022-01-25 14:42 -0800
Re: How to avoid an overflow during multiplication? scott@slp53.sl.home (Scott Lurndal) - 2022-01-25 23:05 +0000
Re: How to avoid an overflow during multiplication? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-01-29 04:54 -0800
Re: How to avoid an overflow during multiplication? James Kuyper <jameskuyper@alumni.caltech.edu> - 2022-01-24 21:50 -0500
Re: How to avoid an overflow during multiplication? Manfred <invalid@invalid.add> - 2022-01-25 19:24 +0100
Re: How to avoid an overflow during multiplication? scott@slp53.sl.home (Scott Lurndal) - 2022-01-25 18:35 +0000
Re: How to avoid an overflow during multiplication? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-01-29 10:05 -0800
Re: How to avoid an overflow during multiplication? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-01-21 20:46 +0000
Re: How to avoid an overflow during multiplication? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-01-21 17:32 -0800
Re: How to avoid an overflow during multiplication? Mateusz Viste <mateusz@xyz.invalid> - 2022-01-22 09:57 +0100
Re: How to avoid an overflow during multiplication? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-01-22 09:44 -0800
Re: How to avoid an overflow during multiplication? James Kuyper <jameskuyper@alumni.caltech.edu> - 2022-01-22 15:26 -0500
Re: How to avoid an overflow during multiplication? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-01-22 14:44 -0800
Re: How to avoid an overflow during multiplication? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-01-21 23:37 -0800
Re: How to avoid an overflow during multiplication? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-01-22 12:04 -0800
Re: How to avoid an overflow during multiplication? Mateusz Viste <mateusz@xyz.invalid> - 2022-01-24 09:59 +0100
Re: How to avoid an overflow during multiplication? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-02-03 10:24 -0800
Re: How to avoid an overflow during multiplication? Mateusz Viste <mateusz@xyz.invalid> - 2022-02-03 21:34 +0100
Re: How to avoid an overflow during multiplication? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2022-02-03 13:33 -0800
Re: How to avoid an overflow during multiplication? Mateusz Viste <mateusz@xyz.invalid> - 2022-02-03 22:57 +0100
Re: How to avoid an overflow during multiplication? Vir Campestris <vir.campestris@invalid.invalid> - 2022-02-03 22:28 +0000
Re: How to avoid an overflow during multiplication? Mateusz Viste <mateusz@xyz.invalid> - 2022-02-03 23:48 +0100
Re: How to avoid an overflow during multiplication? James Kuyper <jameskuyper@alumni.caltech.edu> - 2022-02-03 22:17 -0500
Re: How to avoid an overflow during multiplication? Öö Tiib <ootiib@hot.ee> - 2022-02-04 00:36 -0800
Re: How to avoid an overflow during multiplication? Mateusz Viste <mateusz@xyz.invalid> - 2022-02-04 10:49 +0100
Re: How to avoid an overflow during multiplication? Öö Tiib <ootiib@hot.ee> - 2022-02-04 09:03 -0800
Re: How to avoid an overflow during multiplication? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-02-07 00:52 -0800
Re: How to avoid an overflow during multiplication? Bart <bc@freeuk.com> - 2022-02-07 10:03 +0000
Re: How to avoid an overflow during multiplication? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-02-07 11:22 +0000
Re: How to avoid an overflow during multiplication? Bart <bc@freeuk.com> - 2022-02-07 14:58 +0000
Re: How to avoid an overflow during multiplication? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-02-07 09:06 -0800
Re: How to avoid an overflow during multiplication? Mateusz Viste <mateusz@xyz.invalid> - 2022-02-04 09:44 +0100
Re: How to avoid an overflow during multiplication? David Brown <david.brown@hesbynett.no> - 2022-02-04 11:06 +0100
Re: How to avoid an overflow during multiplication? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2022-02-04 05:53 -0800
Re: How to avoid an overflow during multiplication? David Brown <david.brown@hesbynett.no> - 2022-02-04 15:27 +0100
Re: How to avoid an overflow during multiplication? Mateusz Viste <mateusz@xyz.invalid> - 2022-02-04 15:53 +0100
Re: How to avoid an overflow during multiplication? David Brown <david.brown@hesbynett.no> - 2022-02-05 14:11 +0100
Re: How to avoid an overflow during multiplication? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2022-02-05 09:15 -0800
Re: How to avoid an overflow during multiplication? Bart <bc@freeuk.com> - 2022-02-04 19:38 +0000
Re: How to avoid an overflow during multiplication? David Brown <david.brown@hesbynett.no> - 2022-02-05 14:23 +0100
Re: How to avoid an overflow during multiplication? Bart <bc@freeuk.com> - 2022-02-05 15:16 +0000
Re: How to avoid an overflow during multiplication? David Brown <david.brown@hesbynett.no> - 2022-02-05 17:27 +0100
Re: How to avoid an overflow during multiplication? Bart <bc@freeuk.com> - 2022-02-05 16:41 +0000
Re: How to avoid an overflow during multiplication? David Brown <david.brown@hesbynett.no> - 2022-02-06 12:01 +0100
Re: How to avoid an overflow during multiplication? Bart <bc@freeuk.com> - 2022-02-06 13:24 +0000
Re: How to avoid an overflow during multiplication? Manfred <invalid@add.invalid> - 2022-02-05 23:18 +0100
Re: How to avoid an overflow during multiplication? James Kuyper <jameskuyper@alumni.caltech.edu> - 2022-02-06 00:11 -0500
Re: How to avoid an overflow during multiplication? Manfred <noname@add.invalid> - 2022-02-06 18:43 +0100
Re: How to avoid an overflow during multiplication? David Brown <david.brown@hesbynett.no> - 2022-02-06 15:03 +0100
Re: How to avoid an overflow during multiplication? "james...@alumni.caltech.edu" <jameskuyper@alumni.caltech.edu> - 2022-02-05 09:38 -0800
Re: How to avoid an overflow during multiplication? Bart <bc@freeuk.com> - 2022-02-05 17:57 +0000
Re: How to avoid an overflow during multiplication? Richard Damon <Richard@Damon-Family.org> - 2022-02-05 13:29 -0500
Re: How to avoid an overflow during multiplication? David Brown <david.brown@hesbynett.no> - 2022-02-06 15:15 +0100
Re: How to avoid an overflow during multiplication? Bart <bc@freeuk.com> - 2022-02-06 14:34 +0000
Re: How to avoid an overflow during multiplication? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2022-02-06 12:56 -0800
Re: How to avoid an overflow during multiplication? "james...@alumni.caltech.edu" <jameskuyper@alumni.caltech.edu> - 2022-02-05 09:50 -0800
Re: How to avoid an overflow during multiplication? Bart <bc@freeuk.com> - 2022-02-05 18:09 +0000
Re: How to avoid an overflow during multiplication? James Kuyper <jameskuyper@alumni.caltech.edu> - 2022-02-04 11:06 -0500
Re: How to avoid an overflow during multiplication? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2022-02-04 09:02 -0800
Re: How to avoid an overflow during multiplication? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2022-02-04 11:12 -0800
Re: How to avoid an overflow during multiplication? James Kuyper <jameskuyper@alumni.caltech.edu> - 2022-02-04 19:36 -0500
Re: How to avoid an overflow during multiplication? scott@slp53.sl.home (Scott Lurndal) - 2022-02-04 16:38 +0000
Re: How to avoid an overflow during multiplication? Vir Campestris <vir.campestris@invalid.invalid> - 2022-02-06 22:08 +0000
Re: How to avoid an overflow during multiplication? Mateusz Viste <mateusz@xyz.invalid> - 2022-02-07 09:11 +0100
Re: How to avoid an overflow during multiplication? Mateusz Viste <mateusz@xyz.invalid> - 2022-02-07 09:13 +0100
Re: How to avoid an overflow during multiplication? Mateusz Viste <mateusz@xyz.invalid> - 2022-02-07 09:14 +0100
Re: How to avoid an overflow during multiplication? Vir Campestris <vir.campestris@invalid.invalid> - 2022-02-07 21:42 +0000
Re: How to avoid an overflow during multiplication? Mateusz Viste <mateusz@xyz.invalid> - 2022-02-07 23:43 +0100
Re: How to avoid an overflow during multiplication? James Kuyper <jameskuyper@alumni.caltech.edu> - 2022-02-03 22:35 -0500
Re: How to avoid an overflow during multiplication? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-02-04 21:14 -0800
Re: How to avoid an overflow during multiplication? Mateusz Viste <mateusz@xyz.invalid> - 2022-02-05 11:40 +0100
Re: How to avoid an overflow during multiplication? James Kuyper <jameskuyper@alumni.caltech.edu> - 2022-02-05 13:46 -0500
Re: How to avoid an overflow during multiplication? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-02-05 23:30 +0000
Re: How to avoid an overflow during multiplication? James Kuyper <jameskuyper@alumni.caltech.edu> - 2022-02-06 00:17 -0500
Re: How to avoid an overflow during multiplication? David Brown <david.brown@hesbynett.no> - 2022-02-06 15:21 +0100
Re: How to avoid an overflow during multiplication? dave_thompson_2@comcast.net - 2022-05-14 12:34 -0400
Re: How to avoid an overflow during multiplication? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-05-15 07:19 -0700
Re: How to avoid an overflow during multiplication? Andrey Tarasevich <andreytarasevich@hotmail.com> - 2022-05-14 12:04 -0700
Re: How to avoid an overflow during multiplication? Andrey Tarasevich <andreytarasevich@hotmail.com> - 2022-05-14 12:15 -0700
Re: How to avoid an overflow during multiplication? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-05-15 07:25 -0700
Re: How to avoid an overflow during multiplication? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2021-12-31 15:41 -0800
Re: How to avoid an overflow during multiplication? David Brown <david.brown@hesbynett.no> - 2021-12-31 16:17 +0100
Re: How to avoid an overflow during multiplication? Mateusz Viste <mateusz@xyz.invalid> - 2021-12-31 16:22 +0100
Re: How to avoid an overflow during multiplication? Guillaume <message@bottle.org> - 2021-12-31 19:35 +0100
Re: How to avoid an overflow during multiplication? Bonita Montero <Bonita.Montero@gmail.com> - 2021-12-31 13:53 +0100
Re: How to avoid an overflow during multiplication? Öö Tiib <ootiib@hot.ee> - 2021-12-31 05:10 -0800
Re: How to avoid an overflow during multiplication? Bonita Montero <Bonita.Montero@gmail.com> - 2021-12-31 14:25 +0100
Re: How to avoid an overflow during multiplication? scott@slp53.sl.home (Scott Lurndal) - 2021-12-31 16:16 +0000
Re: How to avoid an overflow during multiplication? Mateusz Viste <mateusz@xyz.invalid> - 2021-12-31 17:32 +0100
Re: How to avoid an overflow during multiplication? Mateusz Viste <mateusz@xyz.invalid> - 2021-12-31 14:31 +0100
Re: How to avoid an overflow during multiplication? Bonita Montero <Bonita.Montero@gmail.com> - 2021-12-31 14:37 +0100
Re: How to avoid an overflow during multiplication? "james...@alumni.caltech.edu" <jameskuyper@alumni.caltech.edu> - 2021-12-31 15:21 -0800
Re: How to avoid an overflow during multiplication? David Brown <david.brown@hesbynett.no> - 2022-01-01 13:50 +0100
Re: How to avoid an overflow during multiplication? Michael S <already5chosen@yahoo.com> - 2022-01-01 10:31 -0800
Re: How to avoid an overflow during multiplication? Bonita Montero <Bonita.Montero@gmail.com> - 2022-01-01 20:03 +0100
Re: How to avoid an overflow during multiplication? Bart <bc@freeuk.com> - 2022-01-01 19:18 +0000
Re: How to avoid an overflow during multiplication? David Brown <david.brown@hesbynett.no> - 2022-01-02 13:38 +0100
Re: How to avoid an overflow during multiplication? Michael S <already5chosen@yahoo.com> - 2021-12-31 05:37 -0800
Re: How to avoid an overflow during multiplication? Mateusz Viste <mateusz@xyz.invalid> - 2021-12-31 14:55 +0100
Re: How to avoid an overflow during multiplication? Michael S <already5chosen@yahoo.com> - 2021-12-31 06:12 -0800
Re: How to avoid an overflow during multiplication? Mateusz Viste <mateusz@xyz.invalid> - 2021-12-31 16:11 +0100
Re: How to avoid an overflow during multiplication? Manfred <noname@add.invalid> - 2021-12-31 20:54 +0100
Re: How to avoid an overflow during multiplication? Mateusz Viste <mateusz@xyz.invalid> - 2021-12-31 21:19 +0100
Re: How to avoid an overflow during multiplication? Kaz Kylheku <480-992-1380@kylheku.com> - 2021-12-31 15:19 +0000
Re: How to avoid an overflow during multiplication? Mateusz Viste <mateusz@xyz.invalid> - 2021-12-31 16:24 +0100
Re: How to avoid an overflow during multiplication? Kaz Kylheku <480-992-1380@kylheku.com> - 2021-12-31 15:13 +0000
Re: How to avoid an overflow during multiplication? Mateusz Viste <mateusz@xyz.invalid> - 2021-12-31 17:00 +0100
Re: How to avoid an overflow during multiplication? Richard Damon <Richard@Damon-Family.org> - 2021-12-31 12:16 -0500
Re: How to avoid an overflow during multiplication? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2021-12-31 10:28 -0800
Re: How to avoid an overflow during multiplication? pa@see.signature.invalid (Pierre Asselin) - 2021-12-31 20:18 +0000
Re: How to avoid an overflow during multiplication? Manfred <noname@add.invalid> - 2021-12-31 21:27 +0100
Re: How to avoid an overflow during multiplication? Mateusz Viste <mateusz@xyz.invalid> - 2021-12-31 21:39 +0100
Re: How to avoid an overflow during multiplication? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-01-20 19:41 -0800
Re: How to avoid an overflow during multiplication? Mateusz Viste <mateusz@xyz.invalid> - 2021-12-31 21:31 +0100
Re: How to avoid an overflow during multiplication? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2021-12-31 17:39 -0800
Re: How to avoid an overflow during multiplication? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-01-02 09:08 -0800
Re: How to avoid an overflow during multiplication? James Kuyper <jameskuyper@alumni.caltech.edu> - 2021-12-31 19:08 -0500
Re: How to avoid an overflow during multiplication? James Kuyper <jameskuyper@alumni.caltech.edu> - 2021-12-31 19:45 -0500
Re: How to avoid an overflow during multiplication? Mateusz Viste <mateusz@xyz.invalid> - 2022-01-01 18:24 +0100
Re: How to avoid an overflow during multiplication? James Kuyper <jameskuyper@alumni.caltech.edu> - 2022-01-01 19:31 -0500
Re: How to avoid an overflow during multiplication? "james...@alumni.caltech.edu" <jameskuyper@alumni.caltech.edu> - 2022-01-01 16:53 -0800
Re: How to avoid an overflow during multiplication? James Kuyper <jameskuyper@alumni.caltech.edu> - 2022-01-04 00:32 -0500
Re: How to avoid an overflow during multiplication? Mateusz Viste <mateusz@xyz.invalid> - 2022-01-04 09:43 +0100
Re: How to avoid an overflow during multiplication? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-01-04 07:20 -0800
Re: How to avoid an overflow during multiplication? Mateusz Viste <mateusz@xyz.invalid> - 2022-01-04 18:19 +0100
Re: How to avoid an overflow during multiplication? James Kuyper <jameskuyper@alumni.caltech.edu> - 2022-01-04 10:50 -0500
Re: How to avoid an overflow during multiplication? Mateusz Viste <mateusz@xyz.invalid> - 2022-01-04 17:37 +0100
Re: How to avoid an overflow during multiplication? James Kuyper <jameskuyper@alumni.caltech.edu> - 2022-01-04 15:01 -0500
Re: How to avoid an overflow during multiplication? Mateusz Viste <mateusz@xyz.invalid> - 2022-01-04 21:45 +0100
Re: How to avoid an overflow during multiplication? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2022-01-04 14:21 -0800
Page 8 of 9 — ← Prev page 1 2 3 4 5 6 7 [8] 9 Next page →
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2021-12-31 14:37 +0100 |
| Message-ID | <sqn13f$n37$1@dont-email.me> |
| In reply to | #164149 |
Am 31.12.2021 um 14:31 schrieb Mateusz Viste: > I should have mentioned what CPU I run this on, my bad. It is an Intel > 80C86. 7 MHz, no FPU. Using 64 bits in any way is not really an option. If a * b overflows you have no option other than using 64 bits if you want to have an exact result.
[toc] | [prev] | [next] | [standalone]
| From | "james...@alumni.caltech.edu" <jameskuyper@alumni.caltech.edu> |
|---|---|
| Date | 2021-12-31 15:21 -0800 |
| Message-ID | <7c025db6-fe06-4083-a71b-a56a390c31ddn@googlegroups.com> |
| In reply to | #164145 |
On Friday, December 31, 2021 at 7:53:24 AM UTC-5, Bonita Montero wrote:
> Am 31.12.2021 um 11:02 schrieb Mateusz Viste:
>
> > uint32_t ticks2time(uint32_t ticks, uint32_t grouplen, uint16_t tempo)
> > {
> > return ticks * tempo / grouplen;
> return (uint32_t)((uint64_t)ticks * (uint64_t)tempo / grouplen);
>
> On x86 f.e. the compiler will still use a 32 * 32 multiplication
> because it sees that the casted value's upper halves are zero.
> And after / grouplen you can safely cast the result to uint32_t.
Do you meant that it will use an instruction that multiplies two 32 bit
quantities and produces the correct 64-bit result? If so, that's nice to know,
but not very important - how they get the right result is generally less
important than getting the right result.
If you mean that they multiply two 32-bit quantities, producing a result
that has only 32 bits, even if the mathematically correct result of the
multiplication would require more than 32 bits to be represented correctly,
then that's very important to know, because that would render the
implementation non-conforming.
[toc] | [prev] | [next] | [standalone]
| From | David Brown <david.brown@hesbynett.no> |
|---|---|
| Date | 2022-01-01 13:50 +0100 |
| Message-ID | <sqpimg$oo6$1@dont-email.me> |
| In reply to | #164179 |
On 01/01/2022 00:21, james...@alumni.caltech.edu wrote:
> On Friday, December 31, 2021 at 7:53:24 AM UTC-5, Bonita Montero wrote:
>> Am 31.12.2021 um 11:02 schrieb Mateusz Viste:
>>
>>> uint32_t ticks2time(uint32_t ticks, uint32_t grouplen, uint16_t tempo)
>>> {
>>> return ticks * tempo / grouplen;
>> return (uint32_t)((uint64_t)ticks * (uint64_t)tempo / grouplen);
>>
>> On x86 f.e. the compiler will still use a 32 * 32 multiplication
>> because it sees that the casted value's upper halves are zero.
>> And after / grouplen you can safely cast the result to uint32_t.
>
> Do you meant that it will use an instruction that multiplies two 32 bit
> quantities and produces the correct 64-bit result? If so, that's nice to know,
> but not very important - how they get the right result is generally less
> important than getting the right result.
It is quite common for ISA's to have multiply instructions that take two
registers as inputs and give a double register output - so for a 32-bit
cpu, you'd get a 32x32 -> 64 bit multiply. And it is common for
compilers, even relatively weak ones, to use such instructions when you
write something like "(uint64_t) a * b", with "a" and "b" being of the
smaller size.
As you say, the important thing is to get the right answer - but it's
nice to know that your compiler is likely to get it in an efficient manner.
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2022-01-01 10:31 -0800 |
| Message-ID | <7e62ed9d-4548-4472-9668-7afc3d45946bn@googlegroups.com> |
| In reply to | #164145 |
On Friday, December 31, 2021 at 2:53:24 PM UTC+2, Bonita Montero wrote:
> Am 31.12.2021 um 11:02 schrieb Mateusz Viste:
>
> > uint32_t ticks2time(uint32_t ticks, uint32_t grouplen, uint16_t tempo)
> > {
> > return ticks * tempo / grouplen;
> return (uint32_t)((uint64_t)ticks * (uint64_t)tempo / grouplen);
>
> On x86 f.e. the compiler will still use a 32 * 32 multiplication
> because it sees that the casted value's upper halves are zero.
> And after / grouplen you can safely cast the result to uint32_t.
It seems like you are confusing x86 with x386, a.k.a. IA32.
[toc] | [prev] | [next] | [standalone]
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2022-01-01 20:03 +0100 |
| Message-ID | <sqq8hp$g6d$1@dont-email.me> |
| In reply to | #164202 |
Am 01.01.2022 um 19:31 schrieb Michael S: >> On x86 f.e. the compiler will still use a 32 * 32 multiplication >> because it sees that the casted value's upper halves are zero. >> And after / grouplen you can safely cast the result to uint32_t. > It seems like you are confusing x86 with x386, a.k.a. IA32. x86 is a common synonym for all x86 and descendant CPUs.
[toc] | [prev] | [next] | [standalone]
| From | Bart <bc@freeuk.com> |
|---|---|
| Date | 2022-01-01 19:18 +0000 |
| Message-ID | <sqq9f1$mh0$1@dont-email.me> |
| In reply to | #164203 |
On 01/01/2022 19:03, Bonita Montero wrote: > Am 01.01.2022 um 19:31 schrieb Michael S: > >>> On x86 f.e. the compiler will still use a 32 * 32 multiplication >>> because it sees that the casted value's upper halves are zero. >>> And after / grouplen you can safely cast the result to uint32_t. > >> It seems like you are confusing x86 with x386, a.k.a. IA32. > > x86 is a common synonym for all x86 and descendant CPUs. Typo? If you meant 8086 and up, then 8086 is a 16-bit processor, which is apparently what the OP is using.
[toc] | [prev] | [next] | [standalone]
| From | David Brown <david.brown@hesbynett.no> |
|---|---|
| Date | 2022-01-02 13:38 +0100 |
| Message-ID | <sqs6cj$kr7$1@dont-email.me> |
| In reply to | #164204 |
On 01/01/2022 20:18, Bart wrote: > On 01/01/2022 19:03, Bonita Montero wrote: >> Am 01.01.2022 um 19:31 schrieb Michael S: >> >>>> On x86 f.e. the compiler will still use a 32 * 32 multiplication >>>> because it sees that the casted value's upper halves are zero. >>>> And after / grouplen you can safely cast the result to uint32_t. >> >>> It seems like you are confusing x86 with x386, a.k.a. IA32. >> >> x86 is a common synonym for all x86 and descendant CPUs. > > Typo? > > If you meant 8086 and up, then 8086 is a 16-bit processor, which is > apparently what the OP is using. Yes, x86 is a common synonym for 80386 and up - either the 32-bit or 64-bit lines. The earlier 16-bit devices are so old that they are rarely seen as physical devices (emulation with DOSBox and the like is more common, especially for old games). They are used sometimes in old embedded systems, and clearly they are still used by hobby users who like a challenge with old hardware.
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2021-12-31 05:37 -0800 |
| Message-ID | <ca774586-49c6-4f46-9dd1-f39df2231dd1n@googlegroups.com> |
| In reply to | #164141 |
On Friday, December 31, 2021 at 12:03:00 PM UTC+2, Mateusz Viste wrote:
> I have this little function:
>
> /* converts an amount of ticks into human time (micro-seconds)
> * timeunits: number of ticks to convert into actual time
> * tempo : the time length (in microseconds) of grouplen ticks
> */
> uint32_t ticks2time(uint32_t ticks, uint32_t grouplen, uint16_t tempo)
> {
> return ticks * tempo / grouplen;
> }
>
> In practical situations the end result of this computation is
> guaranteed to always fit inside an uint32_t, but the above formula
> overflows easily in the (ticks * tempo) part.
>
> The easy & stupid way to avoid this overflow would be this:
>
> return ticks * (tempo / grouplen);
>
> ...but it's obviously not a good solution, since it may loose a lot of
> resolution. The hacky compromise that I currently use is this:
>
> return ticks * (((tempo << 3) / grouplen) >> 3);
>
> It works fine in my practical tests, so I might just as well be done
> with it, but I wonder if there is a cleaner approach to such seemingly
> simple problem?
>
> I should also add that this part of the program is performance
> critical, so I cannot afford branching or any other expensive
> computations. It's also worth noting that "grouplen" is guaranteed to
> be a positive number that never changes across the calls of the
> function (which, in truth, is not even a function, but it was easier to
> format it as such for this exercise).
>
> Mateusz
Couple of questions:
1. You said that grouplen never changes. Does it imply that tempo could change?
2. What is maximal expected value of ticks?
3. If the result is for human consumption, how could it be performance-critical? Humans are sloooooow.
[toc] | [prev] | [next] | [standalone]
| From | Mateusz Viste <mateusz@xyz.invalid> |
|---|---|
| Date | 2021-12-31 14:55 +0100 |
| Message-ID | <sqn24c$14ld$1@gioia.aioe.org> |
| In reply to | #164150 |
2021-12-31 at 05:37 -0800, Michael S wrote: > Couple of questions: > 1. You said that grouplen never changes. Does it imply that tempo > could change? Yes, tempo can change during a song play. > 2. What is maximal expected value of ticks? Hard to say as there is no theoretical limit. In practice I have never seen any value above like 10 * tempo, and tempo maxes out at about 2'000'000 (which translates to 30 BPM in the MIDI world). So we could say that ticks is not expected to go above 20'000'000. > 3. If the result is for human consumption, how could it be > performance-critical? Humans are sloooooow. Not when it comes to hearing frequencies and rhythm. The code is a MIDI scheduler that computes the timing of individual MIDI notes. A millisecond resolution is fine, but anything less starts to sound laggy. This is why I compute everything in microseconds (as does MIDI itself). One of the options I was pondering was to convert all values into 1/10th of milliseconds and do computations on this... But it's an even uglier approach than what I do now. Mateusz
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2021-12-31 06:12 -0800 |
| Message-ID | <d9928f83-2dd3-4943-8938-de5627d9f05fn@googlegroups.com> |
| In reply to | #164153 |
On Friday, December 31, 2021 at 3:55:35 PM UTC+2, Mateusz Viste wrote: > 2021-12-31 at 05:37 -0800, Michael S wrote: > > Couple of questions: > > 1. You said that grouplen never changes. Does it imply that tempo > > could change? > Yes, tempo can change during a song play. Then it's tough. Still, if we can divide it into two parts, something like void SetTempo(uint32_t grouplen, uint16_t tempo) that calculates A = tempo/grouplen B = ((tempo%grouplen) * 128)/grouplen and uint32_t ticks2time(uint32_t ticks) that uses A and B and if SetTempo() is called many times less often than ticks2time() then situation could be improved. > > 2. What is maximal expected value of ticks? > Hard to say as there is no theoretical limit. In practice I have never > seen any value above like 10 * tempo, and tempo maxes out at about > 2'000'000 (which translates to 30 BPM in the MIDI world). So we could > say that ticks is not expected to go above 20'000'000. So, multiplication of ticks by number B in range 0:127 is o.k. > > 3. If the result is for human consumption, how could it be > > performance-critical? Humans are sloooooow. > Not when it comes to hearing frequencies and rhythm. The code is a MIDI > scheduler that computes the timing of individual MIDI notes. A > millisecond resolution is fine, but anything less starts to sound > laggy. This is why I compute everything in microseconds (as does MIDI > itself). One of the options I was pondering was to convert all values > into 1/10th of milliseconds and do computations on this... But it's an > even uglier approach than what I do now. I still don't understand, but so be it. > > Mateusz
[toc] | [prev] | [next] | [standalone]
| From | Mateusz Viste <mateusz@xyz.invalid> |
|---|---|
| Date | 2021-12-31 16:11 +0100 |
| Message-ID | <sqn6j3$1utr$1@gioia.aioe.org> |
| In reply to | #164155 |
2021-12-31 at 06:12 -0800, Michael S wrote:
> On Friday, December 31, 2021 at 3:55:35 PM UTC+2, Mateusz Viste wrote:
> > 2021-12-31 at 05:37 -0800, Michael S wrote:
> > > Couple of questions:
> > > 1. You said that grouplen never changes. Does it imply that tempo
> > > could change?
> > Yes, tempo can change during a song play.
>
> Then it's tough.
There are many constraints, yes.
> Still, if we can divide it into two parts, something like
> void SetTempo(uint32_t grouplen, uint16_t tempo) that calculates
> A = tempo/grouplen
> B = ((tempo%grouplen) * 128)/grouplen
> and
> uint32_t ticks2time(uint32_t ticks) that uses A and B
> and if SetTempo() is called many times less often than ticks2time()
> then situation could be improved.
You mean this, right?
uint32_t A = tempo / grouplen;
uint32_t B = (tempo % grouplen) * 128 / grouplen;
return ticks * A + (ticks * B) / 128;
another way to express it would be this:
return ticks * (tempo / grouplen) +
((ticks * (((tempo % grouplen) << 7) / grouplen)) >> 7);
This is close to my solution with bit shifting, but if I get it right
yours is more resilient to wraparounds as it only shifts a remainder
and not the whole tempo. Thanks for the pointer!
> I still don't understand, but so be it.
Another way to say it would be that the CPU is so slow that it
struggles with its current tasks so it doesn't have much time to fiddle
around with too much math (esp. 32-bit math). :)
Mateusz
[toc] | [prev] | [next] | [standalone]
| From | Manfred <noname@add.invalid> |
|---|---|
| Date | 2021-12-31 20:54 +0100 |
| Message-ID | <sqnn6b$18gn$1@gioia.aioe.org> |
| In reply to | #164156 |
On 12/31/2021 4:11 PM, Mateusz Viste wrote:
> 2021-12-31 at 06:12 -0800, Michael S wrote:
>> On Friday, December 31, 2021 at 3:55:35 PM UTC+2, Mateusz Viste wrote:
>>> 2021-12-31 at 05:37 -0800, Michael S wrote:
>>>> Couple of questions:
>>>> 1. You said that grouplen never changes. Does it imply that tempo
>>>> could change?
>>> Yes, tempo can change during a song play.
>>
>> Then it's tough.
>
> There are many constraints, yes.
>
>> Still, if we can divide it into two parts, something like
>> void SetTempo(uint32_t grouplen, uint16_t tempo) that calculates
>> A = tempo/grouplen
>> B = ((tempo%grouplen) * 128)/grouplen
>> and
>> uint32_t ticks2time(uint32_t ticks) that uses A and B
>> and if SetTempo() is called many times less often than ticks2time()
>> then situation could be improved.
>
> You mean this, right?
>
> uint32_t A = tempo / grouplen;
> uint32_t B = (tempo % grouplen) * 128 / grouplen;
> return ticks * A + (ticks * B) / 128;
>
> another way to express it would be this:
>
> return ticks * (tempo / grouplen) +
> ((ticks * (((tempo % grouplen) << 7) / grouplen)) >> 7);
>
> This is close to my solution with bit shifting, but if I get it right
> yours is more resilient to wraparounds as it only shifts a remainder
> and not the whole tempo. Thanks for the pointer!
Splitting quotient and remainder could be something indeed.
Others have mentioned that, however I'll post the following trivial
modification of one of your early sources:
$ cat tempo2.c
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
int main(int argc, char **argv)
{
if (argc != 4) {
printf("usage: %s ticks tempo grouplen\n", argv[0]);
} else {
uint32_t r1, r2, r3, r4, r5, r6;
uint32_t ticks = atoi(argv[1]);
uint32_t tempo = atoi(argv[2]);
uint32_t grouplen = atoi(argv[3]);
r1 = ticks * tempo / grouplen;
r2 = ticks * (tempo / grouplen);
r3 = (ticks * (((tempo << 3) / grouplen))) >> 3;
r4 = (uint64_t)ticks * (uint64_t)tempo / grouplen;
{
uint32_t quot1 = tempo/grouplen;
uint32_t rem1 = tempo % grouplen;
r5 = ticks*quot1 + (rem1 * ticks)/grouplen;
uint32_t quot2 = ticks/grouplen;
uint32_t rem2 = ticks % grouplen;
r6 = ticks*quot1 + rem1*quot2 + (rem1 * rem2)/grouplen;
}
printf("r1 = %u\nr2 = %u\nr3 = %u\nr4 = %u\nr5 = %u\nr6 = %u\n",
r1, r2, r3, r4, r5, r6);
}
return 0;
}
$ cc -std=c11 -Wall tempo2.c && ./a.out 9120 1090909 15370
r1 = 88429
r2 = 638400
r3 = 646380
r4 = 647305
r5 = 647305
r6 = 647305
Assuming that the final result fits in 32 bits, r5 is exact as long as:
grouplen*ticks < UINT32_MAX
r6 is exact as long as:
grouplen*grouplen < UINT32_MAX
The r5 expression could also be refactored so as to require
grouplen*tempo < UINT32_MAX, but your example is already out of this range.
The expressions are also simple enough to be coded directly in x86 asm,
for example you may know that the 'div' instruction yields quotient and
remainder in one go - however, many decent optimizing compilers may do
the same and more.
>
>> I still don't understand, but so be it.
>
> Another way to say it would be that the CPU is so slow that it
> struggles with its current tasks so it doesn't have much time to fiddle
> around with too much math (esp. 32-bit math). :)
>
> Mateusz
>
[toc] | [prev] | [next] | [standalone]
| From | Mateusz Viste <mateusz@xyz.invalid> |
|---|---|
| Date | 2021-12-31 21:19 +0100 |
| Message-ID | <sqnojq$1ff8$2@gioia.aioe.org> |
| In reply to | #164172 |
2021-12-31 at 20:54 +0100, Manfred wrote: > Splitting quotient and remainder could be something indeed. > Others have mentioned that, however I'll post the following trivial > modification of one of your early sources: Hello Manfred, I've actually got to the (almost) same code on my end. I agree that it is the nicest solution, and precomputing the quotient & remainder is definitely an interesting optimization. Thanks for taking the time to put it in code! Mateusz
[toc] | [prev] | [next] | [standalone]
| From | Kaz Kylheku <480-992-1380@kylheku.com> |
|---|---|
| Date | 2021-12-31 15:19 +0000 |
| Message-ID | <20211231071349.923@kylheku.com> |
| In reply to | #164153 |
On 2021-12-31, Mateusz Viste <mateusz@xyz.invalid> wrote: > Not when it comes to hearing frequencies and rhythm. The code is a MIDI > scheduler that computes the timing of individual MIDI notes. A > millisecond resolution is fine, but anything less starts to sound > laggy. If you stand 3 meters away from your guitar amp stack, it takes 9 milliseconds to hear it due to speed of sound in air. -- TXR Programming Language: http://nongnu.org/txr Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
[toc] | [prev] | [next] | [standalone]
| From | Mateusz Viste <mateusz@xyz.invalid> |
|---|---|
| Date | 2021-12-31 16:24 +0100 |
| Message-ID | <sqn7b3$1utr$3@gioia.aioe.org> |
| In reply to | #164159 |
2021-12-31 at 15:19 -0000, Kaz Kylheku wrote: > On 2021-12-31, Mateusz Viste <mateusz@xyz.invalid> wrote: > > Not when it comes to hearing frequencies and rhythm. The code is a > > MIDI scheduler that computes the timing of individual MIDI notes. A > > millisecond resolution is fine, but anything less starts to sound > > laggy. > > If you stand 3 meters away from your guitar amp stack, it takes 9 > milliseconds to hear it due to speed of sound in air. Sure, lag is fine (in this context), but jitter is not. I guess I should have said "sounds jitterish" in lieu of "sounds laggy". Semantics. :) Mateusz
[toc] | [prev] | [next] | [standalone]
| From | Kaz Kylheku <480-992-1380@kylheku.com> |
|---|---|
| Date | 2021-12-31 15:13 +0000 |
| Message-ID | <20211231062510.664@kylheku.com> |
| In reply to | #164141 |
On 2021-12-31, Mateusz Viste <mateusz@xyz.invalid> wrote:
> I have this little function:
>
> /* converts an amount of ticks into human time (micro-seconds)
> * timeunits: number of ticks to convert into actual time
There is no timeunits parameter; is that ticks?
> * tempo : the time length (in microseconds) of grouplen ticks
> */
> uint32_t ticks2time(uint32_t ticks, uint32_t grouplen, uint16_t tempo)
> {
> return ticks * tempo / grouplen;
> }
Ticks are often longer than a microsecond, so it can be
resonably expected that tempo / grouplen > 1.
E.g. a 1000 Hz timer interrupt produces 1000 us ticks. We multiply
by 1000 to go from ticks to seconds. If ticks can go to UINT32_MAX,
then we cannot go to microseconds in 32 bit.
Therefore, this calculation has an inherent global overflow problem,
even if you address the local overflow in the multiplication.
We need:
(uint64_t) ticks * tempo / grouplen;
Computer Associates (of Accpac: see
https://en.wikipedia.org/wiki/Sage_300#History) used this as an interview
question all the time 30 years ago: how to do this kind of scaling
without overflow when the fraction is <= 1. E.g. for calculating
a percentage: X * 100 / Y, where X <= Y.
(Someone in management had used a calculation like this in displaying
free memory in the application years before that or something and were
super proud of their achievement, like that they are Knuth-level talent
and only such others should ever be hired.)
The trick is simply to scale the fraction X/Y down to make it smaller,
so that the multiplication has the headroom for avoiding overflow.
If we knew gcd(X, Y), we could divide X and Y by that to get an exact
equivalent in lowest terms; but that might be enough to eliminate the
overflow. Or even to do anything at all: what if gcd(X, Y) == 1?
What you can do is right shift X and Y until you have enough headroom
for the multiplication:
/* while the multiplication overflows, scale the fraction down */
while (ticks * tempo < ticks) {
ticks /= 2; /* compiles to a right shift */
grouplen /= 2;
}
/* [here, handle grouplen having vanished to zero] */
return ticks * tempo / grouplen;
> The easy & stupid way to avoid this overflow would be this:
> return ticks * (tempo / grouplen);
If the fraction is greater than 1 but grouplen isn't a divisor of
tempo, it's can be horribly inaccurate.
> ...but it's obviously not a good solution, since it may loose a lot of
> resolution. The hacky compromise that I currently use is this:
That will be completely useless in integer math if the fraction is < 1,
because then tempo / guardian is always zero, and it can be horribly
inaccurate when the fraction is > 1.
Supose tempo were *almost* twice grouplen, like 511/256. That
evaluates to 1. It's almost 100% off.
>
> return ticks * (((tempo << 3) / grouplen) >> 3);
So, if if a fixed shift works, you still want to do the multiplication
first, then division, for a better approximation.
return ticks * (tempo / 8) / (grouplen / 8);
I.e. same as pre-scaling the fraction:
tempo /= 8;
grouplen /= 8; /* could be zero! */
return ticks * tempo / grouplen;
This will only work if you know that the ticks value is always small
enough relative to tempo that three bits of headroom is enough.
E.g in our 511/256 example, after scaling by / 8 we get X * 63 / 64.
It's off, but nowhere near as much.
> computations. It's also worth noting that "grouplen" is guaranteed to
> be a positive number that never changes across the calls of the
> function (which, in truth, is not even a function, but it was easier to
> format it as such for this exercise).
OK, so then there may be a way to check somewhere else that the scaled
value grouplen / 8 is nonzero, to avoid division by zero, without
doing that for every calculation.
--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
[toc] | [prev] | [next] | [standalone]
| From | Mateusz Viste <mateusz@xyz.invalid> |
|---|---|
| Date | 2021-12-31 17:00 +0100 |
| Message-ID | <sqn9ee$1utr$4@gioia.aioe.org> |
| In reply to | #164157 |
2021-12-31 at 15:13 -0000, Kaz Kylheku wrote:
> There is no timeunits parameter; is that ticks?
Yes. I reworked the message a few times before posting to make it as
clear as possible, and of course added mistakes along the way...
> Ticks are often longer than a microsecond, so it can be
> resonably expected that tempo / grouplen > 1.
Actually, ticks are not a unit of time. Tempo is a unit of time
(in MIDI terms it's the length, in microseconds, of a quarter note).
Grouplen is the number of "ticks" (also called "unit time") in a quarter
note (which is also called a "beat").
But this does not matter anyway and I do not want to bore you to death.
In any case you are correct that tempo is likely to be greater than
grouplen, even though in theory it does not have to. Usually there's at
least a 100:1 relation between tempo and grouplen.
> E.g. a 1000 Hz timer interrupt produces 1000 us ticks. We multiply
> by 1000 to go from ticks to seconds. If ticks can go to UINT32_MAX,
> then we cannot go to microseconds in 32 bit.
>
> Therefore, this calculation has an inherent global overflow problem,
> even if you address the local overflow in the multiplication.
Nah, it works just fine. :)
The end result is a number of microseconds that represents the
delta-time of a MIDI note (that is "when will the next note occur").
2^32 microseconds is 71 minutes. I know no MIDI file that has such long
pauses in between notes. Sure, one could craft such abomination, but it
is not my ambition to cover such edge cases.
> What you can do is right shift X and Y until you have enough headroom
> for the multiplication:
>
> /* while the multiplication overflows, scale the fraction down */
> while (ticks * tempo < ticks) {
> ticks /= 2; /* compiles to a right shift */
> grouplen /= 2;
> }
Yes, that would be a good solution, if there was no time constraints.
The above loop is rich on branching and may lead to many
multiplications... That's a lot of cycles (for a 4 MHz CPU).
> > return ticks * (tempo / grouplen);
>
> If the fraction is greater than 1 but grouplen isn't a divisor of
> tempo, it's can be horribly inaccurate.
Yes, it is true. Fortunately in practice tempo is much higher than
grouplen, so the practical accuracy of this computation on "normal"
MIDI files is around 92-98%. Not perfect, but hard to hear. I then
added my bit-shifting hack which bumped accuracy to 98-99% - but with
some theoretical risk of introducing new overflows. Hence I was curious
what other people do in similar circumstances.
> > return ticks * (((tempo << 3) / grouplen) >> 3);
>
> So, if if a fixed shift works, you still want to do the multiplication
> first, then division, for a better approximation.
>
> return ticks * (tempo / 8) / (grouplen / 8);
I didn't thought of that, it's actually pretty neat - and
straightforward, too! With the only risk being that the CPU will burn
in flames if grouplen happens to be < 8 (but that's easy to check out of
the critical loop since grouplen never changes).
> > computations. It's also worth noting that "grouplen" is guaranteed
> > to be a positive number that never changes across the calls of the
> > function (which, in truth, is not even a function, but it was
> > easier to format it as such for this exercise).
>
> OK, so then there may be a way to check somewhere else that the scaled
> value grouplen / 8 is nonzero, to avoid division by zero, without
> doing that for every calculation.
Precisely, yes. I will do tests. Thank you for your input!
Mateusz
[toc] | [prev] | [next] | [standalone]
| From | Richard Damon <Richard@Damon-Family.org> |
|---|---|
| Date | 2021-12-31 12:16 -0500 |
| Message-ID | <rVGzJ.177608$Wkjc.152489@fx35.iad> |
| In reply to | #164162 |
On 12/31/21 11:00 AM, Mateusz Viste wrote:
> 2021-12-31 at 15:13 -0000, Kaz Kylheku wrote:
>> There is no timeunits parameter; is that ticks?
>
> Yes. I reworked the message a few times before posting to make it as
> clear as possible, and of course added mistakes along the way...
>
>> Ticks are often longer than a microsecond, so it can be
>> resonably expected that tempo / grouplen > 1.
>
> Actually, ticks are not a unit of time. Tempo is a unit of time
> (in MIDI terms it's the length, in microseconds, of a quarter note).
> Grouplen is the number of "ticks" (also called "unit time") in a quarter
> note (which is also called a "beat").
>
> But this does not matter anyway and I do not want to bore you to death.
> In any case you are correct that tempo is likely to be greater than
> grouplen, even though in theory it does not have to. Usually there's at
> least a 100:1 relation between tempo and grouplen.
>
>> E.g. a 1000 Hz timer interrupt produces 1000 us ticks. We multiply
>> by 1000 to go from ticks to seconds. If ticks can go to UINT32_MAX,
>> then we cannot go to microseconds in 32 bit.
>>
>> Therefore, this calculation has an inherent global overflow problem,
>> even if you address the local overflow in the multiplication.
>
> Nah, it works just fine. :)
>
> The end result is a number of microseconds that represents the
> delta-time of a MIDI note (that is "when will the next note occur").
> 2^32 microseconds is 71 minutes. I know no MIDI file that has such long
> pauses in between notes. Sure, one could craft such abomination, but it
> is not my ambition to cover such edge cases.
>
>> What you can do is right shift X and Y until you have enough headroom
>> for the multiplication:
>>
>> /* while the multiplication overflows, scale the fraction down */
>> while (ticks * tempo < ticks) {
>> ticks /= 2; /* compiles to a right shift */
>> grouplen /= 2;
>> }
>
> Yes, that would be a good solution, if there was no time constraints.
> The above loop is rich on branching and may lead to many
> multiplications... That's a lot of cycles (for a 4 MHz CPU).
>
>>> return ticks * (tempo / grouplen);
>>
>> If the fraction is greater than 1 but grouplen isn't a divisor of
>> tempo, it's can be horribly inaccurate.
>
> Yes, it is true. Fortunately in practice tempo is much higher than
> grouplen, so the practical accuracy of this computation on "normal"
> MIDI files is around 92-98%. Not perfect, but hard to hear. I then
> added my bit-shifting hack which bumped accuracy to 98-99% - but with
> some theoretical risk of introducing new overflows. Hence I was curious
> what other people do in similar circumstances.
>
>>> return ticks * (((tempo << 3) / grouplen) >> 3);
>>
>> So, if if a fixed shift works, you still want to do the multiplication
>> first, then division, for a better approximation.
>>
>> return ticks * (tempo / 8) / (grouplen / 8);
>
> I didn't thought of that, it's actually pretty neat - and
> straightforward, too! With the only risk being that the CPU will burn
> in flames if grouplen happens to be < 8 (but that's easy to check out of
> the critical loop since grouplen never changes).
>
>>> computations. It's also worth noting that "grouplen" is guaranteed
>>> to be a positive number that never changes across the calls of the
>>> function (which, in truth, is not even a function, but it was
>>> easier to format it as such for this exercise).
>>
>> OK, so then there may be a way to check somewhere else that the scaled
>> value grouplen / 8 is nonzero, to avoid division by zero, without
>> doing that for every calculation.
>
> Precisely, yes. I will do tests. Thank you for your input!
>
>
> Mateusz
>
One thought is that if tempo and grouplen don't change often, that you
could precompute an n and k such that
k = (tempo << n) / grouplen
and
MAX_TICKS * k
doesn't overflow.
Then you compute (ticks * k) >> n for your result.
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2021-12-31 10:28 -0800 |
| Message-ID | <86a6ggzl16.fsf@linuxsc.com> |
| In reply to | #164141 |
Mateusz Viste <mateusz@xyz.invalid> writes:
> I have this little function:
>
> /* converts an amount of ticks into human time (micro-seconds)
> * timeunits: number of ticks to convert into actual time
> * tempo : the time length (in microseconds) of grouplen ticks
> */
> uint32_t ticks2time(uint32_t ticks, uint32_t grouplen, uint16_t tempo)
> {
> return ticks * tempo / grouplen;
> }
>
> In practical situations the end result of this computation is
> guaranteed to always fit inside an uint32_t, but the above formula
> overflows easily in the (ticks * tempo) part. [...]
I haven't followed all the extra information you have given, but
here are some ideas for you to try.
First let me restate the function, with minor lexical changes:
uint32_t
ticks2time( uint32_t ticks, uint32_t scale, uint16_t tempo ){
return ticks * tempo / scale;
}
Next you might not know the identity
a*b/c === a*(b/c) + a*(b%c)/c
Of course multiplication is commutative, so we can also write:
a*b/c === b*(a/c) + b*(a%c)/c
These identities suggest two alternate formulations:
uint32_t
ticks2time( uint32_t ticks, uint32_t scale, uint16_t tempo ){
return ticks*(tempo/scale) + ticks*(tempo%scale)/scale;
}
uint32_t
ticks2time( uint32_t ticks, uint32_t scale, uint16_t tempo ){
return tempo*(ticks/scale) + tempo*(ticks%scale)/scale;
}
If one of these works for you (checking both performance and the
lack of overflow) then great.
If the first one works in terms of avoiding overflow, but is too
slow, then if tempo doesn't change often, we can precompute the
quantities tempo/scale and tempo%scale when tempo changes:
uint16_t tempo_scale_q = tempo/scale;
uint16_t tempo_scale_r = tempo%scale;
void
set_tempo( uint16_t tempo, uint16_t scale ){
tempo_scale_q = tempo / scale;
tempo_scale_r = tempo % scale;
}
uint32_t
ticks2time_2( uint32_t ticks, uint32_t scale ){
return ticks*tempo_scale_q + ticks*tempo_scale_r/scale;
}
which probably will be faster than the original.
Incidentally, if 'scale' (aka grouplen) never changes, if you can
make it be a compile-time constant then the compiler may be able
to turn the division (and remainder) into more efficient
computations, giving better performance.
Please let us know if these techniques turn out to be helpful.
Good luck!
[toc] | [prev] | [next] | [standalone]
| From | pa@see.signature.invalid (Pierre Asselin) |
|---|---|
| Date | 2021-12-31 20:18 +0000 |
| Message-ID | <sqnoim$s74$1@reader1.panix.com> |
| In reply to | #164167 |
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
> [ ... ]
> These identities suggest two alternate formulations:
> uint32_t
> ticks2time( uint32_t ticks, uint32_t scale, uint16_t tempo ){
> return ticks*(tempo/scale) + ticks*(tempo%scale)/scale;
> }
> uint32_t
> ticks2time( uint32_t ticks, uint32_t scale, uint16_t tempo ){
> return tempo*(ticks/scale) + tempo*(ticks%scale)/scale;
> }
I was thinking along those lines myself, except, in Tim's first
formula, using the div() function to compute (tempo/scale) and
(tempo%scale) together.
#include <stdlib.h>
tmp= div(tempo, scale)
return ticks*tmp.quot + (tics*tmp.rem)/scale
Ditto if you use (ticks/scale). div() is in C99. I don't know if
it meets your timing constraints but it could be faster than
computing division and remainder separately.
If (ticks*scale) is more likely to overflow than (tempo*scale),
use Tim's second solution. Otherwise use the first.
[toc] | [prev] | [next] | [standalone]
Page 8 of 9 — ← Prev page 1 2 3 4 5 6 7 [8] 9 Next page →
Back to top | Article view | comp.lang.c
csiph-web