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 10:28:21 -0800
Organization: A noiseless patient Spider
Lines: 77
Message-ID: <86a6ggzl16.fsf@linuxsc.com>
References: <sqmkg9$157v$1@gioia.aioe.org>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Info: reader02.eternal-september.org; posting-host="06b28be905d0d032491ccb4d10c11358"; logging-data="9317"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18OARlqSGWz/7CX2CeF5IQuj4wKeI3J55Q="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:SMxroslwmRGOvCwkLZ0Qv7sx3pU= sha1:vryVE9GqBR6FsI/lz+O4TisnKrA=
Xref: csiph.com comp.lang.c:164167

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!