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 9 of 9 — ← Prev page 1 2 3 4 5 6 7 8 [9]
| From | Manfred <noname@add.invalid> |
|---|---|
| Date | 2021-12-31 21:27 +0100 |
| Message-ID | <sqnp3v$1vle$1@gioia.aioe.org> |
| In reply to | #164173 |
On 12/31/2021 9:18 PM, Pierre Asselin wrote:
> 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.
>
I like C's div as well, but AFAIK it is for signed integers only, unless
I've missed the unsigned counterpart.
[toc] | [prev] | [next] | [standalone]
| From | Mateusz Viste <mateusz@xyz.invalid> |
|---|---|
| Date | 2021-12-31 21:39 +0100 |
| Message-ID | <sqnppu$1ff8$4@gioia.aioe.org> |
| In reply to | #164173 |
2021-12-31 at 20:18 -0000, Pierre Asselin wrote: > 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 That was my first thought as well, but div() is for int, while I work on unsigned longs (because int is only 16 bits wide). I checked the documentation of my compiler, and there is no div() equivalent for unsigned longs. Mateusz
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2022-01-20 19:41 -0800 |
| Message-ID | <867datrc15.fsf@linuxsc.com> |
| In reply to | #164173 |
pa@see.signature.invalid (Pierre Asselin) writes:
> 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. [...]
These days I expect compilers to be smart enough to see that both
the division and the remainder are being computed, and generate
single instruction that produces both values. And if there is no
such instruction then div() probably doesn't help much.
[toc] | [prev] | [next] | [standalone]
| From | Mateusz Viste <mateusz@xyz.invalid> |
|---|---|
| Date | 2021-12-31 21:31 +0100 |
| Message-ID | <sqnpau$1ff8$3@gioia.aioe.org> |
| In reply to | #164167 |
2021-12-31 at 10:28 -0800, Tim Rentsch wrote:
> 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
Hello Tim,
Thank you for the extensive explanations. What you suggest has already
been proposed by Michael S. earlier today (although in a slightly more
opaque version and extra scaling, that I later developed further).
I tested it, and it does work very well.
> 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.
The pre-computation subject has been also mentioned already, but thank
you nonetheless for the nice and self-explanatory example code, that's
very kind of you.
As for being faster than the original - I really doubt it.
The original was this:
return ticks * (tempo / scale);
ie. one division followed by one multiplication. The new optimized
version is two multiplications, one division and one addition. It can
hardly be faster... But of course it has the benefit of a much higher
precision.
Mateusz
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2021-12-31 17:39 -0800 |
| Message-ID | <864k6oz11s.fsf@linuxsc.com> |
| In reply to | #164176 |
Mateusz Viste <mateusz@xyz.invalid> writes:
> 2021-12-31 at 10:28 -0800, Tim Rentsch wrote:
>
>> 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
>
> Hello Tim,
>
> Thank you for the extensive explanations. What you suggest has already
> been proposed by Michael S. earlier today [...]
What can I say, great minds think alike. :)
> I tested it, and it does work very well.
>
>> 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.
>
> The pre-computation subject has been also mentioned already, but thank
> you nonetheless for the nice and self-explanatory example code, that's
> very kind of you.
I try to give lucid explanations. I appreciate you appreciating
them.
> As for being faster than the original - I really doubt it.
> The original was this:
>
> return ticks * (tempo / scale);
>
> ie. one division followed by one multiplication. [...]
Oh, by original I meant my own earlier version:
uint32_t
ticks2time( uint32_t ticks, uint32_t scale, uint16_t tempo ){
return ticks*(tempo/scale) + ticks*(tempo%scale)/scale;
}
in which case I expect the precompute version will indeed be
faster.
One further idea.. after posting it occurred to me that there is
a technique that is guaranteed to give the right answer as long
as the result fits in 32 bits:
uint32_t
ticks2time( uint32_t ticks, uint16_t tempo, uint16_t scale ){
uint32_t th = ticks >> 16;
uint32_t th_tempo = th * tempo;
uint32_t tl = (uint16_t) ticks;
return
(th_tempo / scale << 16) +
((th_tempo % scale << 16) + tl*tempo) / scale;
}
This approach is of course more expensive to compute, but it
might be worth trying, as a sanity check if nothing else.
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2022-01-02 09:08 -0800 |
| Message-ID | <86wnjixdyv.fsf@linuxsc.com> |
| In reply to | #164189 |
Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
[...]
> One further idea.. after posting it occurred to me that there is
> a technique that is guaranteed to give the right answer as long
> as the result fits in 32 bits:
>
> uint32_t
> ticks2time( uint32_t ticks, uint16_t tempo, uint16_t scale ){
> uint32_t th = ticks >> 16;
> uint32_t th_tempo = th * tempo;
> uint32_t tl = (uint16_t) ticks;
> return
> (th_tempo / scale << 16) +
> ((th_tempo % scale << 16) + tl*tempo) / scale;
> }
I must recant this earlier comment. Haste makes bugs.
[toc] | [prev] | [next] | [standalone]
| From | James Kuyper <jameskuyper@alumni.caltech.edu> |
|---|---|
| Date | 2021-12-31 19:08 -0500 |
| Message-ID | <sqo611$vte$1@dont-email.me> |
| In reply to | #164141 |
On 12/31/21 2:21 PM, Stefan Ram wrote:
> Mateusz Viste <mateusz@xyz.invalid> writes:
>> uint32_t ticks2time(uint32_t ticks, uint32_t grouplen, uint16_t tempo)
>> {
>> return ticks * tempo / grouplen;
>> }
>
> In the Web, one can sometimes see the expression
>
> ((a/c)*b)+(a%c)*b/c
>
> for this.
>
> I tried to implement this as "muldiv_experimental" using
> "unsigned char" as a model for "uint32_t". So far, my test
> program reports an error, but it might be an error in my
> implementation or test code ... The following listing has
> long lines with more than 72 characters.
That relies upon the identity that a == (a/c)*c + a%c. That identity
only applies to the types of the operands after the usual arithmetic
conversions (which include the integer promotions). Unless UCHAR_MAX >
INT_MAX (which is permitted, but unlikely) unsigned char will promote to
int, and all calculations will be carried out using int arithmetic, with
an int result. If any of your multiplications produce a result greater
than UCHAR_MAX, information will be lost when you convert the result
back to unsigned char, producing apparent violations of that identity.
For the case you mentioned, a=2, b=128, c=3, if you used int values for
the intermediate results you would have gotten:
p: 2/3 = 0
q: 0*128 = 0
r: 2%3 = 2
m: 2*128 = 256
d: 256/3 = 85
s: 0+85 = 85
However, since you converted the result back to unsigned char, m ends up
with a value of 0 rather than 256.
[toc] | [prev] | [next] | [standalone]
| From | James Kuyper <jameskuyper@alumni.caltech.edu> |
|---|---|
| Date | 2021-12-31 19:45 -0500 |
| Message-ID | <sqo86f$a7j$1@dont-email.me> |
| In reply to | #164183 |
On 12/31/21 7:25 PM, Stefan Ram wrote: > James Kuyper <jameskuyper@alumni.caltech.edu> writes: >> However, since you converted the result back to unsigned char, m ends up >> with a value of 0 rather than 256. > > I believe Mateusz wrote something along the lines of "Using > 64 bits in any way is not really an option.". So, I assumed > that he wanted to use uint32_t throughout, and every of his > binary operations would process two 32 bit values and yield > one 32 bit value. > > I tried to scale the whole thing down from 32 bits to 8 bits > to facilitate observation. That's why I painstakingly converted > every intermediate result back to "unsigned char". Which implies that you didn't think things through properly. Scaling it down to unsigned char introduces a problem (the integer promotions) that would come up with uint32_t only if INT_MAX > UINT32_MAX. I've frequently used systems where 'int' was a 64-bit type, but from the OP's description, that's unlikely to be the case on the platform he's targeting. If you had used unsigned int rather than unsigned char, you would guarantee that the integer promotions could not come into play.
[toc] | [prev] | [next] | [standalone]
| From | Mateusz Viste <mateusz@xyz.invalid> |
|---|---|
| Date | 2022-01-01 18:24 +0100 |
| Message-ID | <sqq2p9$1g77$2@gioia.aioe.org> |
| In reply to | #164187 |
2021-12-31 at 19:45 -0500, James Kuyper wrote: > it down to unsigned char introduces a problem (the integer > promotions) that would come up with uint32_t only if INT_MAX > > UINT32_MAX. I've frequently used systems where 'int' was a 64-bit > type, but from the OP's description, that's unlikely to be the case > on the platform he's targeting. Indeed. The platform is a 40-years old system where ints are 16-bit. Mateusz
[toc] | [prev] | [next] | [standalone]
| From | James Kuyper <jameskuyper@alumni.caltech.edu> |
|---|---|
| Date | 2022-01-01 19:31 -0500 |
| Message-ID | <sqqroj$4ef$1@dont-email.me> |
| In reply to | #164187 |
On 12/31/21 9:30 PM, Stefan Ram wrote: > ram@zedat.fu-berlin.de (Stefan Ram) writes: >> , the exact result for a call with the arguments 2705443, >> 415131524, and 1256275308 would be 894003, so it would > > PS: In the OP, "tempo" has only 16 bits instead of 32. > I did not take this reduced width into account, and used > too many test values. "tempo" corresponds to my "b". > But even when "b" fits into 16 bits, I still get errors: > > q=0, p=0, r=2705443, m=4251374074, m_=17136275962, d=2, s=2 > Error found! > a=2705443 b=6334 c=1736723169: exact_result=9 experimental_result=2 The formula you're using is `a*b/c = ((a/c)*b)+(a%c)*b/c`. This formula is valid only if (a%c)*b doesn't overflow. The value of the formula derives from the fact that there's a wide range of values for `a`, `b`, and `c` for which `a*b` overflows, but `a*b/c` doesn't, and neither does `(a%c)*b`. However, `a=2705443 b=6334 c=1736723169` is not one of those sets, as your own code demonstrates by comparing the value of `m` and `m_`.
[toc] | [prev] | [next] | [standalone]
| From | "james...@alumni.caltech.edu" <jameskuyper@alumni.caltech.edu> |
|---|---|
| Date | 2022-01-01 16:53 -0800 |
| Message-ID | <51bc5c8a-7cd7-4289-880d-7333a280115dn@googlegroups.com> |
| In reply to | #164211 |
On Saturday, January 1, 2022 at 7:31:27 PM UTC-5, james...@alumni.caltech.edu wrote: > On 12/31/21 9:30 PM, Stefan Ram wrote: ... > The formula you're using is `a*b/c = ((a/c)*b)+(a%c)*b/c`. This formula > is valid only if (a%c)*b doesn't overflow. Given what the C standard says about unsigned overflow, that should have been worded differently: "... if the mathematical value of `(a%c)*b` is representable in the type being used for the result."
[toc] | [prev] | [next] | [standalone]
| From | James Kuyper <jameskuyper@alumni.caltech.edu> |
|---|---|
| Date | 2022-01-04 00:32 -0500 |
| Message-ID | <sr0m4h$vu3$1@dont-email.me> |
| In reply to | #164211 |
On 1/1/22 8:58 PM, Stefan Ram wrote:
...
> To determine how large a possible increase in the number of values
> with the correct result is, I wrote a function "muldiv_naive" with
> just "a * b / c" and another function "muldiv_experimental" with
> the formula you mentioned above.
>
> Then I calculate three random numbers a, b, c in a loop and count
> the number of correct results of the naive approach and with the
> formula you mentioned above.
>
> So far, the output of the program shows that the formula you
> mentioned above does indeed yield the correct result in about
> five times more cases than with the naive approach. But on the
> other hand, overall, both find the correct result only in few
> cases if all possible 32 bit values are used for a and c and
> all possible 16 bit values for b.
>
> main.c
>
> #include <limits.h>
> #include <stdint.h>
> #include <stdio.h>
> #include <stdlib.h>
>
> #if RAND_MAX != 32767
> #error "RAND_MAX != 32767"
> #endif
I couldn't use your code unmodified on my system; it has RAND_MAX ==
2147483647.
> #if UINT16_MAX != 65535
> #error "UINT16_MAX != 65535"
> #endif
>
> #if UINT32_MAX != 4294967295
> #error "UINT32_MAX != 4294967295"
> #endif>
> #define TOP ( ( unsigned long long )UINT32_MAX + 1 )
>
> unsigned long long rand32( void )
> { return
> ( ( ( ( unsigned long long )rand() >> 5 )<< 30 )+
> ( ( ( unsigned long long )rand() >> 5 )<< 20 )+
> ( ( ( unsigned long long )rand() >> 5 )<< 10 )+
> ( ( ( unsigned long long )rand() >> 5 )<< 0 ))&
> ( unsigned long long )0xffffffff; }
It would have made more sense to have this return uint32_t, and to use
uint32_t in the calculations.
There's no need to cast the final constant - it's likely to be the
correct type even without the cast, and if it isn't, it will be
implicitly converted to that type anyway, and has a value that will
survive the conversion unchanged.
> unsigned long long rand16( void )
> { return
> ( ( ( ( unsigned long long )rand() >> 5 )<< 10 )+
> ( ( ( unsigned long long )rand() >> 5 )<< 0 ))&
> ( unsigned long long )0xffff; }
Similarly, that should have use uint16_t. And again, there's no need to
cast the final constant, for the same reasons as in rand32().
> void the_exact_result_is_not_representable( void ){}
>
> unsigned long long muldiv_exact
> ( unsigned long long const a,
> unsigned long long const b,
> unsigned long long const c )
> { return a * b / c; }
>
> uint32_t muldiv_naive
> ( uint32_t const a,
> uint16_t const b,
> uint32_t const c )
> { return a * b / c; }
>
> uint32_t muldiv_experimental
> ( uint32_t const a,
> uint16_t const b,
> uint32_t const c )
> { const uint32_t q =( uint32_t )( a / c );
> const uint32_t p =( uint32_t )( q * b );
> const uint32_t r =( uint32_t )( a % c );
> const uint32_t m =( uint32_t )( r * b );
> const uint32_t d =( uint32_t )( m / c );
> const uint32_t s =( uint32_t )( p + d );
Note: those casts are unnecessary - assigning them to variables with
that type causes the same conversion to occur implicitly.
> return s; }
>
> int main( void )
> { unsigned long long naive_correct = 0;
> unsigned long long experimental_correct = 0;
> unsigned long long count = 0;> while( count < 100000000 )
If your count is going to be that small, unsigned long or even long
would be sufficient, there's no need to use unsigned long long for the
counters above.
> { unsigned long long a = rand32();
> unsigned long long b = rand16();
> unsigned long long c = rand32();
Those should have been defined as uint32_t and uint16_t. The only
consequence of defining them as unsigned long long is that it might make
the arithmetic slower - it won't change the calculated results.
> if( c )
> { unsigned long long const exact_result =
> muldiv_exact( a, b, c );
> uint32_t const experimental_result =
> muldiv_experimental( ( uint32_t )a,( uint16_t )b,( uint32_t )c );
> uint32_t const naive_result =
> muldiv_naive( ( uint32_t )a,( uint16_t )b,( uint32_t )c );
Those casts are all unnecessary, with or without the changes I suggested
above, because the specified conversions occur implicitly even without
those casts.
> if( exact_result >= TOP )
> the_exact_result_is_not_representable();
> else
> { if( naive_result == exact_result )
> { ++naive_correct; }
> if( experimental_result == exact_result )
> { ++experimental_correct; }}}
> ++count; }> printf
> ( "count=%llu, naive_correct=%llu, experimental_correct=%llu\n",
> count, naive_correct, experimental_correct );
> printf
> ( "naive percentage: %g\n",
> ( double )naive_correct/( double )count * 100. );
Simpler:
naive_correct * 100.0 / count;
With that change, the needed conversions will occur implicitly, and
similarly for the next calculation:
> printf
> ( "experimental percentage: %g\n",
> ( double )experimental_correct/( double )count * 100. ); }
>
> transcript
>
> count=100000000, naive_correct=19178, experimental_correct=120393
> naive percentage: 0.019178
> experimental percentage: 0.120393
Note first that the experimental percentage is much higher than the
naive percentage, which is what makes that formula useful. The reason
why the experimental percentage is so small is the second term:
(a%c)*b/c. a%c has a value that can be as high as c-1, so the
multiplication has a good chance of wrapping if c > UINT16_MAX,
rendering the formula invalid.
The OP has only given a few indications of the range of values for grouplen:
1. It's passed through a uint32_t interface, implying that it's at least
possible for it to be > UINT16_MAX.
2. He's said it never changes.
3. He gave 15730 as an example of a real-world value.
4. He indicated that tempo/grouplen is typically about 100. Since tempo
is passed as a uint16_t value, that would imply that grouplen is
normally much smaller than UINT16_MAX.
All in all, it sounds likely ticks, tempo, and grouplen usually (though
not necessarily always) have values that allow the formula a*b/c =
(a/c)*b + (a%c)*b/c to be valid when using a 32-bit type.
[toc] | [prev] | [next] | [standalone]
| From | Mateusz Viste <mateusz@xyz.invalid> |
|---|---|
| Date | 2022-01-04 09:43 +0100 |
| Message-ID | <sr11bc$1thv$2@gioia.aioe.org> |
| In reply to | #164258 |
2022-01-04 at 00:32 -0500, James Kuyper wrote: > Simpler: > naive_correct * 100.0 / count; I'm not sure if you guys still talk about the original case, but if so, then there is no FPU on the target system. Ie. floats and doubles are prohibited. Just sayin'. > The OP has only given a few indications of the range of values for > grouplen: 1. It's passed through a uint32_t interface, implying that > it's at least possible for it to be > UINT16_MAX. > 2. He's said it never changes. > 3. He gave 15730 as an example of a real-world value. > 4. He indicated that tempo/grouplen is typically about 100. Since > tempo is passed as a uint16_t value, that would imply that grouplen is > normally much smaller than UINT16_MAX. > > All in all, it sounds likely ticks, tempo, and grouplen usually > (though not necessarily always) have values that allow the formula > a*b/c = (a/c)*b + (a%c)*b/c to be valid when using a 32-bit type. That is correct, yes. In fact even the original formula was working fine on 95%+ of cases: (ticks * tempo) / grouplen It broke up when I've got a file with an unusually high tempo value: 1090909. Now, to clarify the context, here's what the values are really: "grouplen" is a MIDI time division (16-bit): https://www.recordingblogs.com/wiki/time-division-of-a-midi-file "tempo" is a MIDI tempo value (24-bit, but usually between 300 and 1000000): http://midi.teragonaudio.com/tech/midifile/tempo.htm "ticks" is a MIDI delta-time (up to 28 bits, but usually between 0 and 10*tempo): http://midi.teragonaudio.com/tech/midifile/vari.htm Mateusz
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2022-01-04 07:20 -0800 |
| Message-ID | <86bl0ry1ct.fsf@linuxsc.com> |
| In reply to | #164262 |
Mateusz Viste <mateusz@xyz.invalid> writes:
> [ want to compute the value of '(ticks * tempo) / grouplen' ]
>
> [ that expression ] was working fine on 95%+ of cases
>
> It broke up when I've got a file with an unusually high tempo value:
> 1090909.
>
> Now, to clarify the context, here's what the values are really:
>
> "grouplen" is a MIDI time division (16-bit):
> https://www.recordingblogs.com/wiki/time-division-of-a-midi-file
>
> "tempo" is a MIDI tempo value (24-bit, but usually between 300 and
> 1000000):
> http://midi.teragonaudio.com/tech/midifile/tempo.htm
>
> "ticks" is a MIDI delta-time (up to 28 bits, but usually between 0 and
> 10*tempo):
> http://midi.teragonaudio.com/tech/midifile/vari.htm
Given this additional information -- in particular, that ticks
and tempo have 32 bit types, and grouplen has a 16 bit type -- a
more exact calculation suggests itself:
#include <stdint.h>
uint32_t
ticks2time( uint32_t ticks, uint32_t tempo, uint16_t grouplen ){
uint32_t a = ticks, b = tempo, c = grouplen;
uint32_t aq = a/c, ar = a%c, bq = b/c, br = b%c;
return aq*b + ar*bq + ar*br/c;
}
with the usual comments about precomputing 'bq' and 'br', if that
turns out to be important.
This approach should give correct values in all cases when the
result fits in 32 bits.
[toc] | [prev] | [next] | [standalone]
| From | Mateusz Viste <mateusz@xyz.invalid> |
|---|---|
| Date | 2022-01-04 18:19 +0100 |
| Message-ID | <sr1vj2$qv$2@gioia.aioe.org> |
| In reply to | #164270 |
2022-01-04 at 07:20 -0800, Tim Rentsch wrote:
> Given this additional information -- in particular, that ticks
> and tempo have 32 bit types, and grouplen has a 16 bit type -- a
> more exact calculation suggests itself:
>
> #include <stdint.h>
>
> uint32_t
> ticks2time( uint32_t ticks, uint32_t tempo, uint16_t grouplen ){
> uint32_t a = ticks, b = tempo, c = grouplen;
> uint32_t aq = a/c, ar = a%c, bq = b/c, br = b%c;
> return aq*b + ar*bq + ar*br/c;
> }
That is brilliant. You may be interested to know that James Kuyper
arrived to a very similar solution (even though the path he followed
was different).
You might also like to know that your computation is almost 8x faster
than a computation over 64 bits (the target system is a 16-bit, hence
64-bit are very costly, but still). This even without any
pre-computation. I measured it with the test program pasted below, and
it outputs:
t 500 1090909 15360
Tim = 139809378 after 41 clocks
Cast= 139809378 after 323 clocks
Very nice. Thanks!
------ TEST.C ---------------------------------------------
#include <stdio.h>
#include <stdlib.h>
static unsigned long gettime(void) {
unsigned short hw = 0, lw = 0;
unsigned long r;
_asm {
xor ah, ah
int 0x1a
mov hw, cx
mov lw, dx
}
r = (hw << 16) | lw;
return(r);
}
int main(int argc, char **argv) {
unsigned long ticks = atoi(argv[1]);
unsigned long tempo = atoi(argv[2]);
unsigned short grouplen = atoi(argv[3]);
unsigned short i;
unsigned long r, t0, t1;
if (argc != 4) return(1);
t0 = gettime();
for (i = 1; i++; ) {
unsigned long a = ticks, b = tempo, c = grouplen;
unsigned long aq = a/c, ar = a%c, bq = b/c, br = b%c;
r = aq*b + ar*bq + ar*br/c;
}
t1 = gettime();
printf("Tim = %lu after %lu clocks\n", r, t1 - t0);
t0 = gettime();
for (i = 1; i++; ) {
r = (((unsigned long long)ticks * tempo) / grouplen);
}
t1 = gettime();
printf("Cast= %lu after %lu clocks\n", r, t1 - t0);
return(0);
}
-----------------------------------------------------------
Mateusz
[toc] | [prev] | [next] | [standalone]
| From | James Kuyper <jameskuyper@alumni.caltech.edu> |
|---|---|
| Date | 2022-01-04 10:50 -0500 |
| Message-ID | <sr1qc7$6cf$1@dont-email.me> |
| In reply to | #164262 |
On 1/4/22 3:43 AM, Mateusz Viste wrote:
> 2022-01-04 at 00:32 -0500, James Kuyper wrote:
>> Simpler:
>> naive_correct * 100.0 / count;
>
> I'm not sure if you guys still talk about the original case, but if so,
> then there is no FPU on the target system. Ie. floats and doubles are
> prohibited. Just sayin'.
We are talking about the original case, but that line is NOT part of a
proposed solution to your problem. Stephen Ram created a program that
analyzed the results using a proposed solution, and the expression above
is part of the process of displaying the results of that analysis.
>> The OP has only given a few indications of the range of values for
>> grouplen: 1. It's passed through a uint32_t interface, implying that
>> it's at least possible for it to be > UINT16_MAX.
>> 2. He's said it never changes.
>> 3. He gave 15730 as an example of a real-world value.
>> 4. He indicated that tempo/grouplen is typically about 100. Since
>> tempo is passed as a uint16_t value, that would imply that grouplen is
>> normally much smaller than UINT16_MAX.
>>
>> All in all, it sounds likely ticks, tempo, and grouplen usually
>> (though not necessarily always) have values that allow the formula
>> a*b/c = (a/c)*b + (a%c)*b/c to be valid when using a 32-bit type.
>
> That is correct, yes. In fact even the original formula was working
> fine on 95%+ of cases: (ticks * tempo) / grouplen
>
> It broke up when I've got a file with an unusually high tempo value:
> 1090909.
>
> Now, to clarify the context, here's what the values are really:
>
> "grouplen" is a MIDI time division (16-bit):
> https://www.recordingblogs.com/wiki/time-division-of-a-midi-file
>
> "tempo" is a MIDI tempo value (24-bit, but usually between 300 and
> 1000000):
> http://midi.teragonaudio.com/tech/midifile/tempo.htm
>
> "ticks" is a MIDI delta-time (up to 28 bits, but usually between 0 and
> 10*tempo):
> http://midi.teragonaudio.com/tech/midifile/vari.htm
On 12/31/21 5:02 AM, you wrote:
...
> uint32_t ticks2time(uint32_t ticks, uint32_t grouplen, uint16_t tempo)
Based upon what you said above, I assume that the arguments to this
function have the wrong types: grouplen should have been uint16_t, while
tempo should have been uint32_t.
What I said above was based upon the assumption that tempo was a 16-bit
type. Therefore, if grouplen was also normally <= UINT16_MAX, then
(ticks%grouplen)*tempo would not normally wrap around. If tempo needs 24
bits, and grouplen needs 16, then that expression can still wrap around.
However, there is an alternative approach that avoids the problem
entirely. I came up with this approach before Stephen Ram mentioned the
apparently well-know formula:
a*b/c == ((a/c)*b)+(a%c)*b/c
While that formula was unknown to me, it's easy to derive from the
better-known formula:
a = (a/c)*c + a%c
I never mentioned my alternative, because if grouplen is a 32-bit type,
it's just as prone to overflow as the one Stephen mentioned, and roughly
twice as complicated. However, since grouplen is actually a 16-bit type,
it completely avoids that problem. Here's how I derived my alternative:
The following expressions should be considered evaluated in an integer
type big enough so that none of the multiplication ever overflows:
a*b/c == ( (a/c)*c + a%c ) * ( (b/c)*c + b%c) / c
== ( (a/c)*(b/c)*c*c + (a/c)*(b%c)*c + (a%c)*(b/c)*c + (a%c)*(b%c)) / c
Now, while (a/c)*c == a is NOT a valid identity for C's integer
arithmetic, (a*c)/c == a is (in the absence of overflow/wraparound).
Therefore:
a*b/c == (a/c)*(b/c)*c + (a/c)*(b%c) + (a%c)*(b/c) + (a%c)*(b%c)/c
Now, if a and b have the type uint32_t, and c has the type uint16_t, and
they happen to have values such that a*(uint64_t)b/c would be
representable in uint32_t, then none of the terms on the right-hand side
will overflow/wraparound uint32_t, and the final result will be
therefore be exactly the same as if evaluated in uint64_t.
uint32_t ticks2time(uint32_t ticks, uint16_t grouplen, uint32_t tempo)
{
uint32_t tiogr = ticks/grouplen;
uint16_t timgr = ticks%grouplen;
uint32_t teogr = tempo/grouplen;
uint16_t temgr = tempo%grouplen;
return tiogr * teogr * grouplen + tiogr*temgr +
timgr*temgr + timgr*temgr/grouplen;
}
[toc] | [prev] | [next] | [standalone]
| From | Mateusz Viste <mateusz@xyz.invalid> |
|---|---|
| Date | 2022-01-04 17:37 +0100 |
| Message-ID | <sr1t4b$qv$1@gioia.aioe.org> |
| In reply to | #164272 |
2022-01-04 at 10:50 -0500, James Kuyper wrote:
> > uint32_t ticks2time(uint32_t ticks, uint32_t grouplen, uint16_t
> > tempo)
>
> Based upon what you said above, I assume that the arguments to this
> function have the wrong types: grouplen should have been uint16_t,
> while tempo should have been uint32_t.
You are correct, that's an error I must have introduced while
reformatting the code into a function... My stupid mistake.
> I never mentioned my alternative, because if grouplen is a 32-bit
> type, it's just as prone to overflow as the one Stephen mentioned,
> and roughly twice as complicated. However, since grouplen is actually
> a 16-bit type, it completely avoids that problem. Here's how I
> derived my alternative:
> (...)
> uint32_t ticks2time(uint32_t ticks, uint16_t grouplen, uint32_t
> tempo) {
> uint32_t tiogr = ticks/grouplen;
> uint16_t timgr = ticks%grouplen;
> uint32_t teogr = tempo/grouplen;
> uint16_t temgr = tempo%grouplen;
> return tiogr * teogr * grouplen + tiogr*temgr +
> timgr*temgr + timgr*temgr/grouplen;
> }
That is interesting. It is also interesting to note that this part:
tiogr * teogr * grouplen
expands into that:
(ticks/grouplen) * (tempo/grouplen) * grouplen
...where we can drop two grouplens so it becomes:
(ticks/grouplen) * tempo
After this simplification, your formula becomes almost identical to the
one proposed by Tim 30 minutes earlier. :-)
Mateusz
[toc] | [prev] | [next] | [standalone]
| From | James Kuyper <jameskuyper@alumni.caltech.edu> |
|---|---|
| Date | 2022-01-04 15:01 -0500 |
| Message-ID | <sr2936$jej$1@dont-email.me> |
| In reply to | #164274 |
On 1/4/22 11:37 AM, Mateusz Viste wrote:
> 2022-01-04 at 10:50 -0500, James Kuyper wrote:
...
>> I never mentioned my alternative, because if grouplen is a 32-bit
>> type, it's just as prone to overflow as the one Stephen mentioned,
>> and roughly twice as complicated. However, since grouplen is actually
>> a 16-bit type, it completely avoids that problem. Here's how I
>> derived my alternative:
>> (...)
>> uint32_t ticks2time(uint32_t ticks, uint16_t grouplen, uint32_t
>> tempo) {
>> uint32_t tiogr = ticks/grouplen;
>> uint16_t timgr = ticks%grouplen;
>> uint32_t teogr = tempo/grouplen;
>> uint16_t temgr = tempo%grouplen;
>> return tiogr * teogr * grouplen + tiogr*temgr +
>> timgr*temgr + timgr*temgr/grouplen;
>> }
>
> That is interesting. It is also interesting to note that this part:
> tiogr * teogr * grouplen
>
> expands into that:
> (ticks/grouplen) * (tempo/grouplen) * grouplen
>
> ...where we can drop two grouplens so it becomes:
> (ticks/grouplen) * tempo
No, you can't drop them. This is integer arithmetic, not real-number
arithmetic. (20/3)*3 == 6*3 == 18, not 20.
> After this simplification, your formula becomes almost identical to the
> one proposed by Tim 30 minutes earlier. :-)
Tim's version doesn't differ from mine by using the invalid
simplification you suggest. Instead, his version combines what I called
tiogr*teogr*grouple and tiogr*temgr into tiogr*(teogr*grouplen + temgr)
which is equivalent ot tiogr*tempo. If ticks*(uint64_t)tempo/grouplen is
representable as a uint32_t, then tiogr*tempo won't wrap, so that's a
valid simplification, one that I didn't notice.
[toc] | [prev] | [next] | [standalone]
| From | Mateusz Viste <mateusz@xyz.invalid> |
|---|---|
| Date | 2022-01-04 21:45 +0100 |
| Message-ID | <sr2bkp$tdr$1@gioia.aioe.org> |
| In reply to | #164283 |
2022-01-04 at 15:01 -0500, James Kuyper wrote: > > expands into that: > > (ticks/grouplen) * (tempo/grouplen) * grouplen > > > > ...where we can drop two grouplens so it becomes: > > (ticks/grouplen) * tempo > > No, you can't drop them. This is integer arithmetic, not real-number > arithmetic. (20/3)*3 == 6*3 == 18, not 20. You are right of course. I wasn't looking carefully enough and missed that the point was to remove the remainder in this part of the formula. Thank you for the clarification. Mateusz
[toc] | [prev] | [next] | [standalone]
| From | Keith Thompson <Keith.S.Thompson+u@gmail.com> |
|---|---|
| Date | 2022-01-04 14:21 -0800 |
| Message-ID | <87pmp7ywez.fsf@nosuchdomain.example.com> |
| In reply to | #164258 |
James Kuyper <jameskuyper@alumni.caltech.edu> writes:
> On 1/1/22 8:58 PM, Stefan Ram wrote:
[...]
>> unsigned long long rand32( void )
>> { return
>> ( ( ( ( unsigned long long )rand() >> 5 )<< 30 )+
>> ( ( ( unsigned long long )rand() >> 5 )<< 20 )+
>> ( ( ( unsigned long long )rand() >> 5 )<< 10 )+
>> ( ( ( unsigned long long )rand() >> 5 )<< 0 ))&
>> ( unsigned long long )0xffffffff; }
>
> It would have made more sense to have this return uint32_t, and to use
> uint32_t in the calculations.
>
> There's no need to cast the final constant - it's likely to be the
> correct type even without the cast, and if it isn't, it will be
> implicitly converted to that type anyway, and has a value that will
> survive the conversion unchanged.
Or just write the constant as 0xffffffffULL. (Though if you change it
from unsigned long long to one of the uintN_t types it's not that simple.)
[...]
--
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
Working, but not speaking, for Philips
void Void(void) { Void(); } /* The recursive call of the void */
[toc] | [prev] | [standalone]
Page 9 of 9 — ← Prev page 1 2 3 4 5 6 7 8 [9]
Back to top | Article view | comp.lang.c
csiph-web