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!

Le 31/12/2021 à 14:41, Stefan Ram a écrit :
> Mateusz Viste <mateusz@xyz.invalid> wrote:
>> 2021-12-31 at 12:33 +0000, Ben Bacarisse wrote:
>>> There's a technical detail here which is that in C unsigned arithmetic
>>> can't overflow. Arithmetic overflow is reserved for serious undefined
>>> situation. Unsigned arithmetic just "wraps round" in a defined
>>> manner.
>> Can you provide the source please? I know that what you describe is the
>
> |A computation involving unsigned operands can never overflow,
> |because a result that cannot be represented by the resulting
> |unsigned integer type is reduced modulo the number that is
> |one greater than the largest value that can be represented by
> |the resulting type.

Yep. Which, by the way, is a pretty funny way of defining "never
overflowing".

Yes, in C it's very straightforward. Arithmetic operations on unsigned
are always modulo 2^N, with N the number of bits of the resulting type.

So indeed, they can't overflow. The result is just effectively truncated
if it *would* overflow.

Now make sure you understand the implications of doing your operations
modulo 2^N.

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.

main.c

#include <limits.h>
#include <stdio.h>
#include <stdlib.h>

#define TOP (UCHAR_MAX+1)

void the_exact_result_is_not_representable_with_unsigned_char_anyway_so_we_dont_care( void ){}

unsigned long muldiv_exact( const unsigned long a, const unsigned long b, const unsigned long c )
{ return a * b / c; }

unsigned char muldiv_experimental( const unsigned char a, const unsigned char b, const unsigned char c )
{ const unsigned char q =( unsigned char )( a / c );
const unsigned char p =( unsigned char )( q * b );
const unsigned char r =( unsigned char )( a % c );
const unsigned char m =( unsigned char )( r * b );
const unsigned char d =( unsigned char )( m / c );
const unsigned char s =( unsigned char )( p + d );
return s; }

int main( void )
{ for( unsigned long a = 0; a < TOP; ++a )
for( unsigned long b = 0; b < TOP; ++b )
for( unsigned long c = 1; c < TOP; ++c )
{ unsigned long exact_result = muldiv_exact( a,b,c );
unsigned char experimental_result = muldiv_experimental(( unsigned char )a,( unsigned char )b,( unsigned char )c );
if( exact_result >= TOP )
the_exact_result_is_not_representable_with_unsigned_char_anyway_so_we_dont_care();
else
if( exact_result != experimental_result )
{ puts( "Error found!" );
printf( "a=%lu b=%lu c=%lu: exact_result=%lu experimental_result=%u\n", a, b, c, exact_result, experimental_result );
exit( 99 ); }}}

transcript

Error found!
a=2 b=128 c=3: exact_result=85 experimental_result=0

Mateusz Viste <mateusz@xyz.invalid> writes:
> 2021-12-31 at 13:41 GMT, Stefan Ram wrote:
>> |A computation involving unsigned operands can never overflow,
>> |because a result that cannot be represented by the resulting
>> |unsigned integer type is reduced modulo the number that is
>> |one greater than the largest value that can be represented by
>> |the resulting type.
>> n2310, 6.2.5p9
>
> Had missed that one, thanks!
>
> (In my ANSI C copy it is at 6.1.2.5, p23)

You mean ISO C. (C standards have been published by ISO, not ANSI,
since 1990.) Which edition are you using?

It's section 6.2.5 in C99 and later. If you're seeing that paragraph in
section 6.1.2.5, you're probably using the C90 standard (which doesn't
have paragraph numbers, BTW). I suggest grabbing a more recent draft.
N1570 is nearly equivalent to the C11 standard. (There are drafts that
are close to the C17 standard, but most of them are password protected.)

http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf

--
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 */

2021-12-31 at 11:38 -0800, Keith Thompson wrote:
> > (In my ANSI C copy it is at 6.1.2.5, p23)
>
> You mean ISO C. (C standards have been published by ISO, not ANSI,
> since 1990.)

No, I do mean ANSI, although it was a conjoint work with ISO.

> Which edition are you using?

The cover says:

"American National Standard for Programming Languages - C
ANSI/ISO 9899-1990
(revision and redesignation of ANSI X3.159-1989)
Approved August 3, 1992"

> I suggest grabbing a more recent draft. N1570 is nearly equivalent to
> the C11 standard. (There are drafts that are close to the C17
> standard, but most of them are password protected.)

Meh. I'm *really* not interested in those post-1990 atrocities. At all.
Will stay with ANSI C, it worked very well for me so far. Sorry. :-)

Mateusz

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
>

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.

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

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.

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

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

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.

On 12/31/21 2:49 PM, Mateusz Viste wrote:
> 2021-12-31 at 11:38 -0800, Keith Thompson wrote:
>>> (In my ANSI C copy it is at 6.1.2.5, p23)
>>
>> You mean ISO C. (C standards have been published by ISO, not ANSI,
>> since 1990.)
>
> No, I do mean ANSI, although it was a conjoint work with ISO.
>
>> Which edition are you using?
>
> The cover says:
>
> "American National Standard for Programming Languages - C
> ANSI/ISO 9899-1990
> (revision and redesignation of ANSI X3.159-1989)
> Approved August 3, 1992"

Calling it ANSI C is not very useful, because that designation is
ambiguous. Every version of the C standard has been adopted as a
standard by both ANSI and ISO, so referring to ANSI C doesn't make it
clear whether you're referring to C90, C99, C2011, or C2017. That would
be fine if you were referring to any or all four of those versions
collectively - but you do seem to be referring only to C90.

uint32_t and uint16_t, both of which are used in your code, were added
to the language in C99. So apparently you don't consider C99 a complete
atrocity.

Mateusz Viste <mateusz@xyz.invalid> writes:
> 2021-12-31 at 11:38 -0800, Keith Thompson wrote:
>> > (In my ANSI C copy it is at 6.1.2.5, p23)
>>
>> You mean ISO C. (C standards have been published by ISO, not ANSI,
>> since 1990.)
>
> No, I do mean ANSI, although it was a conjoint work with ISO.
>
>> Which edition are you using?
>
> The cover says:
>
> "American National Standard for Programming Languages - C
> ANSI/ISO 9899-1990
> (revision and redesignation of ANSI X3.159-1989)
> Approved August 3, 1992"

The 1990 ISO C standard is nearly equivalent to the 1989 ANSI C
standard. A major difference is that the sections were renumbered. In
the 1989 edition, the core language was in section 3. In the 1990 ISO
standard, it's section 6.

>> I suggest grabbing a more recent draft. N1570 is nearly equivalent to
>> the C11 standard. (There are drafts that are close to the C17
>> standard, but most of them are password protected.)
>
> Meh. I'm *really* not interested in those post-1990 atrocities. At all.
> Will stay with ANSI C, it worked very well for me so far. Sorry. :-)

Strictly speaking, the term "ANSI C" is ambiguous. People often use it
to refer to the language defined by the 1989 ANSI C standard, but in
fact ANSI has officially adopted each new ISO C standard edition and
considers the previous editions to be obsolete. I suggest referring to
"C90" rather than "ANSI C".

--
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 */

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.

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".

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.

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.

James Kuyper <jameskuyper@alumni.caltech.edu> writes: 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

If you wanted to say that the runtime error message would
not occur had uint32_t been used instead of "unsigned char":
I get error messages with uint32_t, too. With

uint32_t muldiv_experimental
( uint32_t const a, uint32_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 uint64_t m_ =( uint64_t )r * b;
const uint32_t d =( uint32_t )( m / c );
const uint32_t s =( uint32_t )( p + d );
printf
( "q=%u, p=%u, r=%u, m=%u, m_=%llu, d=%u, s=%u\n",
q, p, r, m, m_, d, s );
return s; }

, the exact result for a call with the arguments 2705443,
415131524, and 1256275308 would be 894003, so it would
fit into an uint32_t, but muldiv_experimental returns 1.
And the implementation used does not have INT_MAX > UINT32_MAX.

The internal variables for the above argument values are:

q=0, p=0, r=2705443, m=2202617612, m_=1123114675685132, d=1, s=1

. Had m_ been used instead of m, maybe the result would be
correct, but, as I wrote, I believe Mateusz wrote something
like, "Using 64 bits in any way is not really an option.".

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

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.

2021-12-31 at 18:37 -0500, James Kuyper wrote:
> Calling it ANSI C is not very useful, because that designation is
> ambiguous.

I was only stating about "my copy of ANSI C". Didn't mean to specify
any more than that, really.

> uint32_t and uint16_t, both of which are used in your code, were added
> to the language in C99. So apparently you don't consider C99 a
> complete atrocity.

My answer was obviously slightly provocative. In truth, I am no puritan
and I do pick sometime things out of C89, like uint32_t, snprintf() and
the like. I also appreciate __uint128_t very much, even though it is not
part of any standard. For practical purposes I find the gnu89 dialect
to suit me pretty well.

Mateusz

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

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.

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.