Path: csiph.com!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: Tim Rentsch <tr.17687@z991.linuxsc.com>
Newsgroups: comp.lang.c
Subject: Re: How to avoid an overflow during multiplication?
Date: Fri, 31 Dec 2021 17:39:59 -0800
Organization: A noiseless patient Spider
Lines: 67
Message-ID: <864k6oz11s.fsf@linuxsc.com>
References: <sqmkg9$157v$1@gioia.aioe.org> <86a6ggzl16.fsf@linuxsc.com> <sqnpau$1ff8$3@gioia.aioe.org>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Info: reader02.eternal-september.org; posting-host="8d4c26aa7c7194cacc690ff896698f96"; logging-data="25193"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18hxPgUOsmxQkBeJwi55RvlpNl8Ut/nGzQ="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:DdMz21Kf3Vsk9HomCNTlReRsYV0= sha1:VBtLAbIJ8xq54WEnBuFKpNezgoA=
Xref: csiph.com comp.lang.c:164189

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.