Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #164423 > unrolled thread

on an analogy for verifying whether another digit fits (into an unsigned type)

Back to article view | Back to comp.lang.c

Contents

  on an analogy for verifying whether another digit fits (into an unsigned type) Meredith Montgomery <mmontgomery@levado.to> - 2022-01-15 23:27 -0300
    Re: on an analogy for verifying whether another digit fits (into an unsigned type) Bart <bc@freeuk.com> - 2022-01-16 18:44 +0000
      Re: on an analogy for verifying whether another digit fits (into an unsigned type) Meredith Montgomery <mmontgomery@levado.to> - 2022-01-17 09:48 -0300
        Re: on an analogy for verifying whether another digit fits (into an unsigned type) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-01-17 17:27 +0000
          Re: on an analogy for verifying whether another digit fits (into an unsigned type) scott@slp53.sl.home (Scott Lurndal) - 2022-01-17 18:06 +0000
            Re: on an analogy for verifying whether another digit fits (into an unsigned type) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-01-17 20:59 +0000
              Re: on an analogy for verifying whether another digit fits (into an unsigned type) scott@slp53.sl.home (Scott Lurndal) - 2022-01-18 01:01 +0000
          Re: on an analogy for verifying whether another digit fits (into an unsigned type) Meredith Montgomery <mmontgomery@levado.to> - 2022-01-28 22:15 -0300
            Re: on an analogy for verifying whether another digit fits (into an unsigned type) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-01-29 02:36 +0000
              Re: on an analogy for verifying whether another digit fits (into an unsigned type) Meredith Montgomery <mmontgomery@levado.to> - 2022-01-30 09:12 -0300
                Re: on an analogy for verifying whether another digit fits (into an unsigned type) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-01-30 15:13 +0000
    Re: on an analogy for verifying whether another digit fits (into an unsigned type) Öö Tiib <ootiib@hot.ee> - 2022-01-16 12:15 -0800
      Re: on an analogy for verifying whether another digit fits (into an unsigned type) Meredith Montgomery <mmontgomery@levado.to> - 2022-01-17 09:53 -0300
        Re: on an analogy for verifying whether another digit fits (into an unsigned type) Meredith Montgomery <mmontgomery@levado.to> - 2022-01-17 10:12 -0300
    Re: on an analogy for verifying whether another digit fits (into an unsigned type) Bonita Montero <Bonita.Montero@gmail.com> - 2022-01-19 08:52 +0100
      Re: on an analogy for verifying whether another digit fits (into an unsigned type) Öö Tiib <ootiib@hot.ee> - 2022-01-19 06:08 -0800
        Re: on an analogy for verifying whether another digit fits (into an unsigned type) Bonita Montero <Bonita.Montero@gmail.com> - 2022-01-19 16:31 +0100
          Re: on an analogy for verifying whether another digit fits (into an unsigned type) Bonita Montero <Bonita.Montero@gmail.com> - 2022-01-19 18:02 +0100
            Re: on an analogy for verifying whether another digit fits (into an unsigned type) Bart <bc@freeuk.com> - 2022-01-19 18:27 +0000
              Re: on an analogy for verifying whether another digit fits (into an unsigned type) Bonita Montero <Bonita.Montero@gmail.com> - 2022-01-19 19:44 +0100
                Re: on an analogy for verifying whether another digit fits (into an unsigned type) Bonita Montero <Bonita.Montero@gmail.com> - 2022-01-20 08:08 +0100
                  Re: on an analogy for verifying whether another digit fits (into an unsigned type) Öö Tiib <ootiib@hot.ee> - 2022-01-20 09:47 -0800
              Re: on an analogy for verifying whether another digit fits (into an unsigned type) scott@slp53.sl.home (Scott Lurndal) - 2022-01-19 18:46 +0000
                Re: on an analogy for verifying whether another digit fits (into an unsigned type) Bart <bc@freeuk.com> - 2022-01-19 20:59 +0000
                  Re: on an analogy for verifying whether another digit fits (into an unsigned type) scott@slp53.sl.home (Scott Lurndal) - 2022-01-19 21:12 +0000
                    Re: on an analogy for verifying whether another digit fits (into an unsigned type) Bart <bc@freeuk.com> - 2022-01-19 22:25 +0000
                      Re: on an analogy for verifying whether another digit fits (into an unsigned type) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-01-20 03:49 +0000
                        Re: on an analogy for verifying whether another digit fits (into an unsigned type) Bart <bc@freeuk.com> - 2022-01-20 10:05 +0000
                          Re: on an analogy for verifying whether another digit fits (into an unsigned type) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-01-20 17:02 +0000
                            Re: on an analogy for verifying whether another digit fits (into an unsigned type) Bart <bc@freeuk.com> - 2022-01-20 19:20 +0000
                              Re: on an analogy for verifying whether another digit fits (into an unsigned type) Bart <bc@freeuk.com> - 2022-01-20 19:31 +0000
                  Re: on an analogy for verifying whether another digit fits (into an unsigned type) Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2022-01-23 14:26 -0800
                    Re: on an analogy for verifying whether another digit fits (into an unsigned type) Bart <bc@freeuk.com> - 2022-01-24 00:13 +0000
                      Re: on an analogy for verifying whether another digit fits (into an unsigned type) Lew Pitcher <lew.pitcher@digitalfreehold.ca> - 2022-01-24 00:38 +0000
                        Re: on an analogy for verifying whether another digit fits (into an unsigned type) Bart <bc@freeuk.com> - 2022-01-24 01:09 +0000
                      Re: on an analogy for verifying whether another digit fits (into an unsigned type) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-01-24 01:15 +0000
                        Re: on an analogy for verifying whether another digit fits (into an unsigned type) Bart <bc@freeuk.com> - 2022-01-24 11:21 +0000
                          Re: on an analogy for verifying whether another digit fits (into an unsigned type) scott@slp53.sl.home (Scott Lurndal) - 2022-01-24 15:54 +0000
                            Re: on an analogy for verifying whether another digit fits (into an unsigned type) Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2022-01-24 13:08 -0800
                              Re: on an analogy for verifying whether another digit fits (into an unsigned type) scott@slp53.sl.home (Scott Lurndal) - 2022-01-24 22:51 +0000
                          Re: on an analogy for verifying whether another digit fits (into an unsigned type) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-01-24 15:57 +0000
                            Re: on an analogy for verifying whether another digit fits (into an unsigned type) Bart <bc@freeuk.com> - 2022-01-24 16:52 +0000
                              Re: on an analogy for verifying whether another digit fits (into an unsigned type) Öö Tiib <ootiib@hot.ee> - 2022-01-24 10:17 -0800
                                Re: on an analogy for verifying whether another digit fits (into an unsigned type) scott@slp53.sl.home (Scott Lurndal) - 2022-01-24 18:23 +0000
                          Re: on an analogy for verifying whether another digit fits (into an unsigned type) Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2022-01-24 13:15 -0800
                        Re: on an analogy for verifying whether another digit fits (into an unsigned type) Bart <bc@freeuk.com> - 2022-01-24 11:51 +0000
                      Re: on an analogy for verifying whether another digit fits (into an unsigned type) Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2022-01-23 17:38 -0800
                        Re: on an analogy for verifying whether another digit fits (into an unsigned type) Bart <bc@freeuk.com> - 2022-01-24 11:22 +0000
                      Re: on an analogy for verifying whether another digit fits (into an unsigned type) scott@slp53.sl.home (Scott Lurndal) - 2022-01-24 15:51 +0000
                        Re: on an analogy for verifying whether another digit fits (into an unsigned type) Bart <bc@freeuk.com> - 2022-01-24 22:03 +0000
                          Re: on an analogy for verifying whether another digit fits (into an unsigned type) Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2022-01-24 15:33 -0800
                            Re: on an analogy for verifying whether another digit fits (into an unsigned type) Bart <bc@freeuk.com> - 2022-01-25 00:09 +0000
                              Re: on an analogy for verifying whether another digit fits (into an unsigned type) Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2022-01-24 21:14 -0800
                              Re: on an analogy for verifying whether another digit fits (into an unsigned type) Manfred <invalid@invalid.add> - 2022-01-26 21:01 +0100
                                Re: on an analogy for verifying whether another digit fits (into an unsigned type) Bart <bc@freeuk.com> - 2022-01-26 20:53 +0000
                                  Re: on an analogy for verifying whether another digit fits (into an unsigned type) Manfred <noname@add.invalid> - 2022-01-27 03:42 +0100
    Re: on an analogy for verifying whether another digit fits (into an unsigned type) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-01-20 19:24 -0800
      Re: on an analogy for verifying whether another digit fits (into an unsigned type) Bonita Montero <Bonita.Montero@gmail.com> - 2022-01-21 08:07 +0100
        Re: on an analogy for verifying whether another digit fits (into an unsigned type) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-01-21 06:01 -0800
          Re: on an analogy for verifying whether another digit fits (into an unsigned type) Bonita Montero <Bonita.Montero@gmail.com> - 2022-01-21 17:59 +0100
            Re: on an analogy for verifying whether another digit fits (into an unsigned type) scott@slp53.sl.home (Scott Lurndal) - 2022-01-21 17:41 +0000
              Re: on an analogy for verifying whether another digit fits (into an unsigned type) Bonita Montero <Bonita.Montero@gmail.com> - 2022-01-21 19:26 +0100
            Re: on an analogy for verifying whether another digit fits (into an unsigned type) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-01-21 17:12 -0800
      Re: on an analogy for verifying whether another digit fits (into an unsigned type) Meredith Montgomery <mmontgomery@levado.to> - 2022-01-28 22:25 -0300

Page 1 of 4  [1] 2 3 4  Next page →

#164423 — on an analogy for verifying whether another digit fits (into an unsigned type)

I've been trying to think of an analogy for the verification

      if( ((UINT64_MAX - c) / 10) >= r) 
        r = r * 10 + c;
      else return -1; /* doesn't fit */

in the procedure below.  

I thought of the following, which doesn't quite work.  Consider fill up
a bucker of water where we must make sure not to overflow.  We're given
one last glass of water to throw in the bucket and we need a strategy to
know whether that last glass would or would not overflow the bucket.  We
have all the quantities involved --- the maximum volume in the bucket,
the volume of the glass of water and the volume currently in the bucket.
Say the maximum is M, r is the current volume and c is the volume of
water in the glass.  The subtraction M - c represents the amount of
water that would be the exact amount to fill up the bucket completely
without a drop overflowing if we add c to the bucket.  So, if the
current volume is greater than M - c, then we can't put c in the bucket.

That gives the general strategy, but it's not too good because there's
nothing in this analogy that matches the division by 10.  I could of
course make a up world in which every glass of water you throw in a
bucket makes the volume in the bucket to be multiplied by a factor of 10
before the glass of water goes in.  The purpose of an analogy is to make
something odd look natural, so this is a poor analogy.

Any cool ideas?  Thank you.

(*) The procedure

uint64_t array_to_uint64(char *s, uint64_t *u) 
{
  uint64_t pos;
  uint64_t r;
  uint64_t c;

  pos = 0; r = 0;

  for ( ;; ) {
    c = (uint64_t) (unsigned char) (s[pos] - '0');
    if (c < 10) {
      if( ((UINT64_MAX - c) / 10) >= r) 
        r = r * 10 + c;
      else return -1; /* doesn't fit */
      ++pos; continue;
    }
    break;
  }

  *u = r;
  return pos;
}

[toc] | [next] | [standalone]

#164429

On 16/01/2022 02:27, Meredith Montgomery wrote:
> uint64_t array_to_uint64(char *s, uint64_t *u)
> {
>    uint64_t pos;
>    uint64_t r;
>    uint64_t c;
> 
>    pos = 0; r = 0;
> 
>    for ( ;; ) {
>      c = (uint64_t) (unsigned char) (s[pos] - '0');
>      if (c < 10) {
>        if( ((UINT64_MAX - c) / 10) >= r)

Dividing by 10 each time is unnecessary (even if usually optimised to 
shifts and multiplies).

You only need to make this check after you've already processed 19 
characters, as it could overflow on the 20th, but not before.

I think when pos >= 18.

[toc] | [prev] | [next] | [standalone]

#164442

Bart <bc@freeuk.com> writes:

> On 16/01/2022 02:27, Meredith Montgomery wrote:
>> uint64_t array_to_uint64(char *s, uint64_t *u)
>> {
>>    uint64_t pos;
>>    uint64_t r;
>>    uint64_t c;
>>    pos = 0; r = 0;
>>    for ( ;; ) {
>>      c = (uint64_t) (unsigned char) (s[pos] - '0');
>>      if (c < 10) {
>>        if( ((UINT64_MAX - c) / 10) >= r)
>
> Dividing by 10 each time is unnecessary (even if usually optimised to
> shifts and multiplies).
>
> You only need to make this check after you've already processed 19
> characters, as it could overflow on the 20th, but not before.
>
> I think when pos >= 18.

I suppose you're right, but imagine putting such check there.  It would
take even more paragraphs to explain it to myself some time later when
I'm trying to figure out what I wrote a while back.

[toc] | [prev] | [next] | [standalone]

#164447

Meredith Montgomery <mmontgomery@levado.to> writes:

> Bart <bc@freeuk.com> writes:
>
>> On 16/01/2022 02:27, Meredith Montgomery wrote:
>>> uint64_t array_to_uint64(char *s, uint64_t *u)
>>> {
>>>    uint64_t pos;
>>>    uint64_t r;
>>>    uint64_t c;
>>>    pos = 0; r = 0;
>>>    for ( ;; ) {
>>>      c = (uint64_t) (unsigned char) (s[pos] - '0');
>>>      if (c < 10) {
>>>        if( ((UINT64_MAX - c) / 10) >= r)
>>
>> Dividing by 10 each time is unnecessary (even if usually optimised to
>> shifts and multiplies).
>>
>> You only need to make this check after you've already processed 19
>> characters, as it could overflow on the 20th, but not before.
>>
>> I think when pos >= 18.
>
> I suppose you're right, but imagine putting such check there.  It would
> take even more paragraphs to explain it to myself some time later when
> I'm trying to figure out what I wrote a while back.

You could just check that the array contains a string of digits
lexicographically less than or equal to 18446744073709551615.  If there
are fewer digits than this, or, at every position, the digit you have is
no greater than the corresponding digit of that number, you are ok.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#164448

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>Meredith Montgomery <mmontgomery@levado.to> writes:
>
>> Bart <bc@freeuk.com> writes:
>>
>>> On 16/01/2022 02:27, Meredith Montgomery wrote:
>>>> uint64_t array_to_uint64(char *s, uint64_t *u)
>>>> {
>>>>    uint64_t pos;
>>>>    uint64_t r;
>>>>    uint64_t c;
>>>>    pos = 0; r = 0;
>>>>    for ( ;; ) {
>>>>      c = (uint64_t) (unsigned char) (s[pos] - '0');
>>>>      if (c < 10) {
>>>>        if( ((UINT64_MAX - c) / 10) >= r)
>>>
>>> Dividing by 10 each time is unnecessary (even if usually optimised to
>>> shifts and multiplies).
>>>
>>> You only need to make this check after you've already processed 19
>>> characters, as it could overflow on the 20th, but not before.
>>>
>>> I think when pos >= 18.
>>
>> I suppose you're right, but imagine putting such check there.  It would
>> take even more paragraphs to explain it to myself some time later when
>> I'm trying to figure out what I wrote a while back.
>
>You could just check that the array contains a string of digits
>lexicographically less than or equal to 18446744073709551615.  If there
>are fewer digits than this, or, at every position, the digit you have is
>no greater than the corresponding digit of that number, you are ok.

That reminds me of an algorithm used on BCD mainframes to do addition
and subtraction on large (up to 100 digit) variable length operands.

The most significant digit was stored as the lowest addressed digit (nibble).

The algorithm handled addition and subtraction of two variable length
operands (with overflow detection) with a single pass starting from the
most significant digit of each operand.

   "The processor uses an adder that accumulates two
    fields from the most sigificant to the least significant
    digit positions.   Reverse addition ... has the advantage of
    detecting an overflow condition prior to altering the
    receiving field for the result"

   "If the data fields are signed, sign manipulation takes place
    prior to the addition since they are the most significant digits."

Fundamentally, the algorithm sign/zero extends the smaller operand
and adds a digit from each operand; if carry occurs and if all prior additions
(if any) had summed to nine, overflow is signaled and the operation completes.

To avoid writing to the receiving field before overflow is detected,
the processor had a nines-counter which counted the number of leading
digits each having the value 9.  Once a digit no longer sums to 9 or has
a carry, the BCD digit '9' is flushed to the receiving field until the nines
counter is zero.   The most recent digit sum is stored in a register
to accomodate carry (add one to the register, flush it, and move current
result to register).

1025475_B2500_B3500_RefMan_Oct69.pdf (flowchart p. 5-11)

[toc] | [prev] | [next] | [standalone]

#164456

scott@slp53.sl.home (Scott Lurndal) writes:

> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>>Meredith Montgomery <mmontgomery@levado.to> writes:
>>
>>> Bart <bc@freeuk.com> writes:
>>>
>>>> On 16/01/2022 02:27, Meredith Montgomery wrote:
>>>>> uint64_t array_to_uint64(char *s, uint64_t *u)
>>>>> {
>>>>>    uint64_t pos;
>>>>>    uint64_t r;
>>>>>    uint64_t c;
>>>>>    pos = 0; r = 0;
>>>>>    for ( ;; ) {
>>>>>      c = (uint64_t) (unsigned char) (s[pos] - '0');
>>>>>      if (c < 10) {
>>>>>        if( ((UINT64_MAX - c) / 10) >= r)
>>>>
>>>> Dividing by 10 each time is unnecessary (even if usually optimised to
>>>> shifts and multiplies).
>>>>
>>>> You only need to make this check after you've already processed 19
>>>> characters, as it could overflow on the 20th, but not before.
>>>>
>>>> I think when pos >= 18.
>>>
>>> I suppose you're right, but imagine putting such check there.  It would
>>> take even more paragraphs to explain it to myself some time later when
>>> I'm trying to figure out what I wrote a while back.
>>
>>You could just check that the array contains a string of digits
>>lexicographically less than or equal to 18446744073709551615.  If there
>>are fewer digits than this, or, at every position, the digit you have is
>>no greater than the corresponding digit of that number, you are ok.
>
> That reminds me of an algorithm used on BCD mainframes to do addition
> and subtraction on large (up to 100 digit) variable length operands.
>
> The most significant digit was stored as the lowest addressed digit (nibble).
>
> The algorithm handled addition and subtraction of two variable length
> operands (with overflow detection) with a single pass starting from the
> most significant digit of each operand.
>
>    "The processor uses an adder that accumulates two
>     fields from the most sigificant to the least significant
>     digit positions.   Reverse addition ... has the advantage of
>     detecting an overflow condition prior to altering the
>     receiving field for the result"
>
>    "If the data fields are signed, sign manipulation takes place
>     prior to the addition since they are the most significant digits."
>
> Fundamentally, the algorithm sign/zero extends the smaller operand
> and adds a digit from each operand; if carry occurs and if all prior additions
> (if any) had summed to nine, overflow is signaled and the operation completes.
>
> To avoid writing to the receiving field before overflow is detected,
> the processor had a nines-counter which counted the number of leading
> digits each having the value 9.  Once a digit no longer sums to 9 or has
> a carry, the BCD digit '9' is flushed to the receiving field until the nines
> counter is zero.   The most recent digit sum is stored in a register
> to accomodate carry (add one to the register, flush it, and move current
> result to register).
>
> 1025475_B2500_B3500_RefMan_Oct69.pdf (flowchart p. 5-11)

Interesting.  Thanks.

Unrelated, but I noticed this gem in the list of the system's
advantages:

 d. Programming so simple it can be started by one programmer and
    finished by another

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#164465

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>scott@slp53.sl.home (Scott Lurndal) writes:
>
>> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

>>>
>>>You could just check that the array contains a string of digits
>>>lexicographically less than or equal to 18446744073709551615.  If there
>>>are fewer digits than this, or, at every position, the digit you have is
>>>no greater than the corresponding digit of that number, you are ok.
>>
>> That reminds me of an algorithm used on BCD mainframes to do addition
>> and subtraction on large (up to 100 digit) variable length operands.
>>
>> The most significant digit was stored as the lowest addressed digit (nibble).
>>
>> The algorithm handled addition and subtraction of two variable length
>> operands (with overflow detection) with a single pass starting from the
>> most significant digit of each operand.
>>
>>    "The processor uses an adder that accumulates two
>>     fields from the most sigificant to the least significant
>>     digit positions.   Reverse addition ... has the advantage of
>>     detecting an overflow condition prior to altering the
>>     receiving field for the result"
>>
>>    "If the data fields are signed, sign manipulation takes place
>>     prior to the addition since they are the most significant digits."
>>
>> Fundamentally, the algorithm sign/zero extends the smaller operand
>> and adds a digit from each operand; if carry occurs and if all prior additions
>> (if any) had summed to nine, overflow is signaled and the operation completes.
>>
>> To avoid writing to the receiving field before overflow is detected,
>> the processor had a nines-counter which counted the number of leading
>> digits each having the value 9.  Once a digit no longer sums to 9 or has
>> a carry, the BCD digit '9' is flushed to the receiving field until the nines
>> counter is zero.   The most recent digit sum is stored in a register
>> to accomodate carry (add one to the register, flush it, and move current
>> result to register).
>>
>> 1025475_B2500_B3500_RefMan_Oct69.pdf (flowchart p. 5-11)
>
>Interesting.  Thanks.
>
>Unrelated, but I noticed this gem in the list of the system's
>advantages:
>
> d. Programming so simple it can be started by one programmer and
>    finished by another

Indeed, it was quite simple to program.   Reading a memory
dump was a breeze:

RECD NO   FILE: TRKTAP                     EOF =      394                       7/27/2021 (TUESDAY)   17:05   PAGE 0001            

      1    40F87AF2F8 4000100064 0790000000 6430017400 4001000000 0010010426 94C2000064 0000060768 5600100007 7972000000            
             8 : 2 8                                                         m B                              `                     
(00100)    0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0003000064            
                                                                                                                       ...00100/001 
      2    E3D9D2E3C1 D7F0F0F0F0 F0F0F0F0F0 F0F0F0F0F0 F0F0F0F0F0 F0F0F0F0F0 F0F0F0F0F0 F0F0F0F0F0 F0F0F0F0F0 F0F0F0F0F0            
           T R K T A  P 0 0 0 0  0 0 0 0 0  0 0 0 0 0  0 0 0 0 0  0 0 0 0 0  0 0 0 0 0  0 0 0 0 0  0 0 0 0 0  0 0 0 0 0             
(00100)    F0F0F0F0F0 F0F0F0F0F0 F0F0F0F0F0 F0F0F0F0F0 F0F0F0F0F0 F0F0F0F0F0 F0F0F0F0F0 F0F0F0F0F0 F0F0F0F0F0 F0F0F0F0F0            
           0 0 0 0 0  0 0 0 0 0  0 0 0 0 0  0 0 0 0 0  0 0 0 0 0  0 0 0 0 0  0 0 0 0 0  0 0 0 0 0  0 0 0 0 0  0 0 0 0 0...00100/001 
      3    E3D76DD6E4 E340404040 4040D7D9D6 C6C9D30400 0040404040 4040E00149 6001600000 00000000C4 C9E2D24040 0040404040            
           T P _ O U  T              P R O  F I L                     \      -   -              D  I S K                            
(00100)    4040404040 4040404040 4040400000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000            
                                                                                                                       ...00100/001 
      4    D7D9C9D5E3 4040404040 4040D7D9E3 E3D9D20200 0040404040 4040E00600 8001600000 00000000C4 C9E2D24040 0040404040            
           P R I N T                 P R T  T R K                     \          -              D  I S K                            
(00100)    4040404040 4040404040 4040400000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000            
                                                                                                                       ...00100/001 
      5    E3D9D2E3C1 D740404040 4040E3D9D2 E3C1D70400 0040404040 4040E00668 0001600000 00000000C4 C9E2D24040 0040404040            
           T R K T A  P              T R K  T A P                     \          -              D  I S K                            
(00100)    4040404040 4040404040 4040400000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000            
                                                                                                                       ...00100/001 
Decoding the instruction stream was trivial by eye:

0547000E        LIX       IX1           IX4                         Save table address     003104 670740   100008                   
0548000E         Validate(IX2,"+ERR-6:")                 /Validate Address                                                          
0548000M        MVW       IX2           -VRqst                      Set request ptr        003116 120002   000016   C00340          
0548000M        MVN       +ERR-6     LL -VLab                       Set error label        003134 11A606   004446   C00348          
0548000M        VEN       -Vparm        Valid                       Do the validation      003152 350007   E00340 0D008356          
0549000E                                                                                                                            
0550000E        MVW       RQ-CSD   X2   STRCSD   X7                 Set descriptor         003172 120005   800004 4E000002          
0551000E        MPY  05   BADR       SZ TBL-RN   X4   IX1           Branch table offset    003192 05A502   000060 4D000004   100008 
0552000E        INC       DOVRD1        IX1                         Make code relative     003218 010707   100108   100008          

note the MPY instruction:
  Opcode = 05
  AFBF   = A502   (A Field and B field lengths, bcd; AF=A5 (5 digit unsigned literal), BF=02
  A      = 000060 (Literal 6 encoded in address field)
  B      = 4D000004 (Four digits from the base of Index Register 4)
  C      = 100008   (Signed 7 (AF + BF) digit result at address 8 in memory, which is also IX1)

[toc] | [prev] | [next] | [standalone]

#164702

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> Meredith Montgomery <mmontgomery@levado.to> writes:
>
>> Bart <bc@freeuk.com> writes:
>>
>>> On 16/01/2022 02:27, Meredith Montgomery wrote:
>>>> uint64_t array_to_uint64(char *s, uint64_t *u)
>>>> {
>>>>    uint64_t pos;
>>>>    uint64_t r;
>>>>    uint64_t c;
>>>>    pos = 0; r = 0;
>>>>    for ( ;; ) {
>>>>      c = (uint64_t) (unsigned char) (s[pos] - '0');
>>>>      if (c < 10) {
>>>>        if( ((UINT64_MAX - c) / 10) >= r)
>>>
>>> Dividing by 10 each time is unnecessary (even if usually optimised to
>>> shifts and multiplies).
>>>
>>> You only need to make this check after you've already processed 19
>>> characters, as it could overflow on the 20th, but not before.
>>>
>>> I think when pos >= 18.
>>
>> I suppose you're right, but imagine putting such check there.  It would
>> take even more paragraphs to explain it to myself some time later when
>> I'm trying to figure out what I wrote a while back.
>
> You could just check that the array contains a string of digits
> lexicographically less than or equal to 18446744073709551615.  If there
> are fewer digits than this, or, at every position, the digit you have is
> no greater than the corresponding digit of that number, you are ok.

That seems correct, but if I change the size of my register, then I must
replace the number too. :-)

[toc] | [prev] | [next] | [standalone]

#164707

Meredith Montgomery <mmontgomery@levado.to> writes:

> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>
>> Meredith Montgomery <mmontgomery@levado.to> writes:
>>
>>> Bart <bc@freeuk.com> writes:
>>>
>>>> On 16/01/2022 02:27, Meredith Montgomery wrote:
>>>>> uint64_t array_to_uint64(char *s, uint64_t *u)
>>>>> {
>>>>>    uint64_t pos;
>>>>>    uint64_t r;
>>>>>    uint64_t c;
>>>>>    pos = 0; r = 0;
>>>>>    for ( ;; ) {
>>>>>      c = (uint64_t) (unsigned char) (s[pos] - '0');
>>>>>      if (c < 10) {
>>>>>        if( ((UINT64_MAX - c) / 10) >= r)
>>>>
>>>> Dividing by 10 each time is unnecessary (even if usually optimised to
>>>> shifts and multiplies).
>>>>
>>>> You only need to make this check after you've already processed 19
>>>> characters, as it could overflow on the 20th, but not before.
>>>>
>>>> I think when pos >= 18.
>>>
>>> I suppose you're right, but imagine putting such check there.  It would
>>> take even more paragraphs to explain it to myself some time later when
>>> I'm trying to figure out what I wrote a while back.
>>
>> You could just check that the array contains a string of digits
>> lexicographically less than or equal to 18446744073709551615.  If there
>> are fewer digits than this, or, at every position, the digit you have is
>> no greater than the corresponding digit of that number, you are ok.
>
> That seems correct, but if I change the size of my register, then I must
> replace the number too. :-)

Sure.  Just as you'd have to replace UINT64_MAX and so on.  Remember you
don't have to write 18446744073709551615.  You could use snprintf to put
UINT64_MAX into a static buffer.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#164730

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> Meredith Montgomery <mmontgomery@levado.to> writes:
>
>> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>>
>>> Meredith Montgomery <mmontgomery@levado.to> writes:
>>>
>>>> Bart <bc@freeuk.com> writes:
>>>>
>>>>> On 16/01/2022 02:27, Meredith Montgomery wrote:
>>>>>> uint64_t array_to_uint64(char *s, uint64_t *u)
>>>>>> {
>>>>>>    uint64_t pos;
>>>>>>    uint64_t r;
>>>>>>    uint64_t c;
>>>>>>    pos = 0; r = 0;
>>>>>>    for ( ;; ) {
>>>>>>      c = (uint64_t) (unsigned char) (s[pos] - '0');
>>>>>>      if (c < 10) {
>>>>>>        if( ((UINT64_MAX - c) / 10) >= r)
>>>>>
>>>>> Dividing by 10 each time is unnecessary (even if usually optimised to
>>>>> shifts and multiplies).
>>>>>
>>>>> You only need to make this check after you've already processed 19
>>>>> characters, as it could overflow on the 20th, but not before.
>>>>>
>>>>> I think when pos >= 18.
>>>>
>>>> I suppose you're right, but imagine putting such check there.  It would
>>>> take even more paragraphs to explain it to myself some time later when
>>>> I'm trying to figure out what I wrote a while back.
>>>
>>> You could just check that the array contains a string of digits
>>> lexicographically less than or equal to 18446744073709551615.  If there
>>> are fewer digits than this, or, at every position, the digit you have is
>>> no greater than the corresponding digit of that number, you are ok.
>>
>> That seems correct, but if I change the size of my register, then I must
>> replace the number too. :-)
>
> Sure.  Just as you'd have to replace UINT64_MAX and so on.  Remember you
> don't have to write 18446744073709551615.  You could use snprintf to put
> UINT64_MAX into a static buffer.

Lol.  You're totally right.  It's totally trivial to solve this problem.
Good to know.  I will take notice of this.  I value trivial solutions
quite a lot: I had to think hard about that verification and there was
this easy solution on my face all along.

[toc] | [prev] | [next] | [standalone]

#164738

Meredith Montgomery <mmontgomery@levado.to> writes:

> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>
>> Meredith Montgomery <mmontgomery@levado.to> writes:
>>
>>> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>>>
>>>> Meredith Montgomery <mmontgomery@levado.to> writes:
>>>>
>>>>> Bart <bc@freeuk.com> writes:
>>>>>
>>>>>> On 16/01/2022 02:27, Meredith Montgomery wrote:
>>>>>>> uint64_t array_to_uint64(char *s, uint64_t *u)
>>>>>>> {
>>>>>>>    uint64_t pos;
>>>>>>>    uint64_t r;
>>>>>>>    uint64_t c;
>>>>>>>    pos = 0; r = 0;
>>>>>>>    for ( ;; ) {
>>>>>>>      c = (uint64_t) (unsigned char) (s[pos] - '0');
>>>>>>>      if (c < 10) {
>>>>>>>        if( ((UINT64_MAX - c) / 10) >= r)
>>>>>>
>>>>>> Dividing by 10 each time is unnecessary (even if usually optimised to
>>>>>> shifts and multiplies).
>>>>>>
>>>>>> You only need to make this check after you've already processed 19
>>>>>> characters, as it could overflow on the 20th, but not before.
>>>>>>
>>>>>> I think when pos >= 18.
>>>>>
>>>>> I suppose you're right, but imagine putting such check there.  It would
>>>>> take even more paragraphs to explain it to myself some time later when
>>>>> I'm trying to figure out what I wrote a while back.
>>>>
>>>> You could just check that the array contains a string of digits
>>>> lexicographically less than or equal to 18446744073709551615.  If there
>>>> are fewer digits than this, or, at every position, the digit you have is
>>>> no greater than the corresponding digit of that number, you are ok.
>>>
>>> That seems correct, but if I change the size of my register, then I must
>>> replace the number too. :-)
>>
>> Sure.  Just as you'd have to replace UINT64_MAX and so on.  Remember you
>> don't have to write 18446744073709551615.  You could use snprintf to put
>> UINT64_MAX into a static buffer.
>
> Lol.  You're totally right.  It's totally trivial to solve this problem.
> Good to know.  I will take notice of this.  I value trivial solutions
> quite a lot: I had to think hard about that verification and there was
> this easy solution on my face all along.

There may be pitfalls I've not spotted because I've never seen this done
in anyone else's code.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#164430

On Sunday, 16 January 2022 at 04:28:22 UTC+2, Meredith Montgomery wrote:
> Any cool ideas? Thank you. 

It can not be cool or something as decimal system is arbitrary and
nothing in real world (besides count of human fingers) suggests to
use it. I can try ...

If we want to take 10 times as lot of water as we currently have plus
some then it makes sense to first try if the current water (together with
1/10th of "plus some") fits into 10 times smaller bucket.

But it is unclear if that analogy helps to clarify anything. 

[toc] | [prev] | [next] | [standalone]

#164443

Öö Tiib <ootiib@hot.ee> writes:

> On Sunday, 16 January 2022 at 04:28:22 UTC+2, Meredith Montgomery wrote:
>> Any cool ideas? Thank you. 
>
> It can not be cool or something as decimal system is arbitrary and
> nothing in real world (besides count of human fingers) suggests to
> use it. I can try ...
>
> If we want to take 10 times as lot of water as we currently have plus
> some then it makes sense to first try if the current water (together with
> 1/10th of "plus some") fits into 10 times smaller bucket.
>
> But it is unclear if that analogy helps to clarify anything. 

Hey, I think that helps: we're at least reading out (more clearly) what
we're doing in the arithmetic expression.  I'll go with that for now.
Thank you with so much.

[toc] | [prev] | [next] | [standalone]

#164444

Meredith Montgomery <mmontgomery@levado.to> writes:

> Öö Tiib <ootiib@hot.ee> writes:
>
>> On Sunday, 16 January 2022 at 04:28:22 UTC+2, Meredith Montgomery wrote:
>>> Any cool ideas? Thank you. 
>>
>> It can not be cool or something as decimal system is arbitrary and
>> nothing in real world (besides count of human fingers) suggests to
>> use it. I can try ...
>>
>> If we want to take 10 times as lot of water as we currently have plus
>> some then it makes sense to first try if the current water (together with
>> 1/10th of "plus some") fits into 10 times smaller bucket.
>>
>> But it is unclear if that analogy helps to clarify anything. 
>
> Hey, I think that helps: we're at least reading out (more clearly) what
> we're doing in the arithmetic expression.  I'll go with that for now.
> Thank you with so much.

Hm.  A good analogy here is anything with a certain exponential growth
because base-10 numbers grow exponentially.  So I guess a colony of
bacteria would do.  I can say whenever I add, say, c amount food to the
colony, they multiply themselves by 10 and (remarkably) c new members
are born too.  (Researchers are investigating why.)  Also astounding is
the fact that once they get very near UINT64_MAX members, they just stop
growing no matter what --- baffling the biologists.  The exact condition
is that if the new population size would exceed UINT64_MAX, the c amount
of food does nothing at all.  (They stop eating at that point and
everything stays at it is.)

That's probably the best I can do.

[toc] | [prev] | [next] | [standalone]

#164474

How about that. I wrote it with g++ and it should fit with clang++:

#include <iostream>
#include <stdexcept>
#include <string>

using namespace std;

unsigned long long parseUll( char const *str )
{
	using ull_t = unsigned long long;
	ull_t value = 0;
	for( unsigned char const *scn = (unsigned char const *)str; *scn; ++scn )
	{
		if( __builtin_umulll_overflow( value, 10, &value ) )
			throw overflow_error( "parseUll overflow" );;
		if( __builtin_uaddll_overflow( value, *scn - '0', &value ) )
			throw overflow_error( "parseUll overflow" );;
	}
	return value;
}

int main()
{
	for( ; ; )
		try
		{
			string strValue;
			cin >> strValue;
			cout << parseUll( strValue.c_str() ) << endl;
		}
		catch( overflow_error & )
		{
			cout << "overflow" << endl;
		}
}

[toc] | [prev] | [next] | [standalone]

#164475

On Wednesday, 19 January 2022 at 09:52:58 UTC+2, Bonita Montero wrote:
> How about that. I wrote it with g++ and it should fit with clang++: 
> 

The analogy that OP asked for was likely meant from real word not from
other programming language. 

[toc] | [prev] | [next] | [standalone]

#164476

Am 19.01.2022 um 15:08 schrieb Öö Tiib:
> On Wednesday, 19 January 2022 at 09:52:58 UTC+2, Bonita Montero wrote:
>> How about that. I wrote it with g++ and it should fit with clang++:
>>
> 
> The analogy that OP asked for was likely meant from real word not from
> other programming language.

It's just about the principle; the code can be easily ported to C.

[toc] | [prev] | [next] | [standalone]

#164477

Am 19.01.2022 um 16:31 schrieb Bonita Montero:

> Am 19.01.2022 um 15:08 schrieb Öö Tiib:

>> On Wednesday, 19 January 2022 at 09:52:58 UTC+2, Bonita Montero wrote:

>>> How about that. I wrote it with g++ and it should fit with clang++:
>>>

>> The analogy that OP asked for was likely meant from real word not from
>> other programming language.

> It's just about the principle; the code can be easily ported to C.

Here's a slightly better implementation with improvements for MSVC
with a benchmark.

#include <iostream>
#include <stdexcept>
#include <string>
#include <string>
#include <vector>
#include <random>
#include <sstream>
#include <chrono>
#include <immintrin.h>

using namespace std;
using namespace chrono;

#if defined(_MSC_VER)
__declspec(noinline)
#elif defined(__GNUC__)
__attribute__((noinline))
#endif
unsigned long long parseUll( char const *str )
{
	unsigned long long value = 0;
	for( ; *str; ++str )
	{
#if (!defined(__llvm__) && defined(__GNUC__) && !defined(_MSC_VER)) || 
defined(PARSE_ULL_SIMPLE)
		if( value * 10 / 10 != value )
			goto overflow;
		value *= 10;
		unsigned char digit = *str - '0';
		if( value + digit < value )
			goto overflow;
		value += digit;
#elif defined(__llvm__) || defined(__GNUC__)
		if( __builtin_umulll_overflow( value, 10, &value ) )
			goto overflow;
		if( __builtin_uaddll_overflow( value, (unsigned char)*str - '0', &value) )
			goto overflow;
#elif defined(_MSC_VER)
		unsigned long long hi;
		value = _mulx_u64( value, 10, &hi );
		if( hi )
			goto overflow;
		// _addcarry_u64 specified but missing (MSVC 2022)
		if( value + ((unsigned char)*str - '0') < value )
			goto overflow;
		value += (unsigned char)*str - '0';
#endif
	}
	return value;
overflow:
	throw overflow_error( "parseUll() overflow" );
}

unsigned long long volatile vSum;

int main()
{
	constexpr size_t N = 1000;
	vector<string> rNums;
	rNums.reserve( N );
	mt19937_64 mt;
	uniform_int_distribution<unsigned long long> uidValues( 0, -1 );
	ostringstream oss;
	for( size_t i = 0; i != N; ++i )
	{
		oss.str( "" );
		oss << uidValues( mt );
		rNums.emplace_back( oss.str() );
	}
	unsigned long long sum = 0;
	auto start = high_resolution_clock::now();
	for( size_t i = 0; i != 1000; ++i )
		for( string &str : rNums )
			sum += parseUll( str.c_str() );
	::vSum = sum;
	double ns = (int64_t)duration_cast<nanoseconds>( 
high_resolution_clock::now() - start ).count() / (1000.0 * N);
	cout << ns << endl;
}

[toc] | [prev] | [next] | [standalone]

#164478

On 19/01/2022 17:02, Bonita Montero wrote:
> Am 19.01.2022 um 16:31 schrieb Bonita Montero:
> 
>> Am 19.01.2022 um 15:08 schrieb Öö Tiib:
> 
>>> On Wednesday, 19 January 2022 at 09:52:58 UTC+2, Bonita Montero wrote:
> 
>>>> How about that. I wrote it with g++ and it should fit with clang++:
>>>>
> 
>>> The analogy that OP asked for was likely meant from real word not from
>>> other programming language.
> 
>> It's just about the principle; the code can be easily ported to C.
> 
> Here's a slightly better implementation with improvements for MSVC
> with a benchmark.
> 
> #include <iostream>
> #include <stdexcept>
> #include <string>
> #include <string>
> #include <vector>
> #include <random>
> #include <sstream>
> #include <chrono>
> #include <immintrin.h>
> 
> using namespace std;
> using namespace chrono;
> 
> #if defined(_MSC_VER)
> __declspec(noinline)
> #elif defined(__GNUC__)
> __attribute__((noinline))
> #endif
> unsigned long long parseUll( char const *str )
> {
>      unsigned long long value = 0;
>      for( ; *str; ++str )
>      {
> #if (!defined(__llvm__) && defined(__GNUC__) && !defined(_MSC_VER)) || 
> defined(PARSE_ULL_SIMPLE)
>          if( value * 10 / 10 != value )
>              goto overflow;
>          value *= 10;
>          unsigned char digit = *str - '0';
>          if( value + digit < value )
>              goto overflow;
>          value += digit;
> #elif defined(__llvm__) || defined(__GNUC__)
>          if( __builtin_umulll_overflow( value, 10, &value ) )
>              goto overflow;
>          if( __builtin_uaddll_overflow( value, (unsigned char)*str - 
> '0', &value) )
>              goto overflow;
> #elif defined(_MSC_VER)
>          unsigned long long hi;
>          value = _mulx_u64( value, 10, &hi );
>          if( hi )
>              goto overflow;
>          // _addcarry_u64 specified but missing (MSVC 2022)
>          if( value + ((unsigned char)*str - '0') < value )
>              goto overflow;
>          value += (unsigned char)*str - '0';
> #endif
>      }
>      return value;
> overflow:
>      throw overflow_error( "parseUll() overflow" );
> }
> 
> unsigned long long volatile vSum;
> 
> int main()
> {
>      constexpr size_t N = 1000;
>      vector<string> rNums;
>      rNums.reserve( N );
>      mt19937_64 mt;
>      uniform_int_distribution<unsigned long long> uidValues( 0, -1 );
>      ostringstream oss;
>      for( size_t i = 0; i != N; ++i )
>      {
>          oss.str( "" );
>          oss << uidValues( mt );
>          rNums.emplace_back( oss.str() );
>      }
>      unsigned long long sum = 0;
>      auto start = high_resolution_clock::now();
>      for( size_t i = 0; i != 1000; ++i )
>          for( string &str : rNums )
>              sum += parseUll( str.c_str() );
>      ::vSum = sum;
>      double ns = (int64_t)duration_cast<nanoseconds>( 
> high_resolution_clock::now() - start ).count() / (1000.0 * N);
>      cout << ns << endl;
> }

Complicated. I used the simpler **C** code below. It's runtime was 10% 
slower than the C++ (that is, elapsed time of the 10,000 outer loop for 
both).

(Building the C++ took 3.3 seconds; building the C even with a slow gcc 
took 0.32 seconds. Faster C compilers do it instantly.)

My version calls strlen on the string (which is also assumed here to 
contain the number without signs, leading zeros, and to end on the last 
digit).

In practice this information will often already be known. If I modify 
parseull() to take a length (here emulated with a table of precalculated 
values), then the C version is 25% faster than your C++.

Maybe your C++ version can also benefit from knowing the length, but I 
can't see how from the way it's written.


------------------------------------------------------------

     u64 parseull(char* s) {
         int length=strlen(s);

         if (length>20 || (length==20 && strcmp(s, 
"18446744073709551615")>0)) {
             puts("Overflow"); exit(1);
         }

         u64 a=*s -'0';
         while (--length) {a=a*10+*++s-'0';};
         return a;
     }

     int main(void) {
         u64 a;
         volatile u64 sum=0;

         for (int j=0; j<10000; ++j) {
             for (int i=0; i<1000; ++i) {
                 sum+=parseull(numbers[i]);
             }
         }

         printf("%llu\n",sum);
     }

[toc] | [prev] | [next] | [standalone]

#164479

Am 19.01.2022 um 19:27 schrieb Bart:
> On 19/01/2022 17:02, Bonita Montero wrote:
>> Am 19.01.2022 um 16:31 schrieb Bonita Montero:
>>
>>> Am 19.01.2022 um 15:08 schrieb Öö Tiib:
>>
>>>> On Wednesday, 19 January 2022 at 09:52:58 UTC+2, Bonita Montero wrote:
>>
>>>>> How about that. I wrote it with g++ and it should fit with clang++:
>>>>>
>>
>>>> The analogy that OP asked for was likely meant from real word not from
>>>> other programming language.
>>
>>> It's just about the principle; the code can be easily ported to C.
>>
>> Here's a slightly better implementation with improvements for MSVC
>> with a benchmark.
>>
>> #include <iostream>
>> #include <stdexcept>
>> #include <string>
>> #include <string>
>> #include <vector>
>> #include <random>
>> #include <sstream>
>> #include <chrono>
>> #include <immintrin.h>
>>
>> using namespace std;
>> using namespace chrono;
>>
>> #if defined(_MSC_VER)
>> __declspec(noinline)
>> #elif defined(__GNUC__)
>> __attribute__((noinline))
>> #endif
>> unsigned long long parseUll( char const *str )
>> {
>>      unsigned long long value = 0;
>>      for( ; *str; ++str )
>>      {
>> #if (!defined(__llvm__) && defined(__GNUC__) && !defined(_MSC_VER)) || 
>> defined(PARSE_ULL_SIMPLE)
>>          if( value * 10 / 10 != value )
>>              goto overflow;
>>          value *= 10;
>>          unsigned char digit = *str - '0';
>>          if( value + digit < value )
>>              goto overflow;
>>          value += digit;
>> #elif defined(__llvm__) || defined(__GNUC__)
>>          if( __builtin_umulll_overflow( value, 10, &value ) )
>>              goto overflow;
>>          if( __builtin_uaddll_overflow( value, (unsigned char)*str - 
>> '0', &value) )
>>              goto overflow;
>> #elif defined(_MSC_VER)
>>          unsigned long long hi;
>>          value = _mulx_u64( value, 10, &hi );
>>          if( hi )
>>              goto overflow;
>>          // _addcarry_u64 specified but missing (MSVC 2022)
>>          if( value + ((unsigned char)*str - '0') < value )
>>              goto overflow;
>>          value += (unsigned char)*str - '0';
>> #endif
>>      }
>>      return value;
>> overflow:
>>      throw overflow_error( "parseUll() overflow" );
>> }
>>
>> unsigned long long volatile vSum;
>>
>> int main()
>> {
>>      constexpr size_t N = 1000;
>>      vector<string> rNums;
>>      rNums.reserve( N );
>>      mt19937_64 mt;
>>      uniform_int_distribution<unsigned long long> uidValues( 0, -1 );
>>      ostringstream oss;
>>      for( size_t i = 0; i != N; ++i )
>>      {
>>          oss.str( "" );
>>          oss << uidValues( mt );
>>          rNums.emplace_back( oss.str() );
>>      }
>>      unsigned long long sum = 0;
>>      auto start = high_resolution_clock::now();
>>      for( size_t i = 0; i != 1000; ++i )
>>          for( string &str : rNums )
>>              sum += parseUll( str.c_str() );
>>      ::vSum = sum;
>>      double ns = (int64_t)duration_cast<nanoseconds>( 
>> high_resolution_clock::now() - start ).count() / (1000.0 * N);
>>      cout << ns << endl;
>> }
> 
> Complicated. I used the simpler **C** code below. It's runtime was 10% 
> slower than the C++ (that is, elapsed time of the 10,000 outer loop for 
> both).
> 
> (Building the C++ took 3.3 seconds; building the C even with a slow gcc 
> took 0.32 seconds. Faster C compilers do it instantly.)
> 
> My version calls strlen on the string (which is also assumed here to 
> contain the number without signs, leading zeros, and to end on the last 
> digit).
> 
> In practice this information will often already be known. If I modify 
> parseull() to take a length (here emulated with a table of precalculated 
> values), then the C version is 25% faster than your C++.
> 
> Maybe your C++ version can also benefit from knowing the length, but I 
> can't see how from the way it's written.
> 
> 
> ------------------------------------------------------------
> 
>      u64 parseull(char* s) {
>          int length=strlen(s);
> 
>          if (length>20 || (length==20 && strcmp(s, 
> "18446744073709551615")>0)) {
>              puts("Overflow"); exit(1);
>          }
> 
>          u64 a=*s -'0';
>          while (--length) {a=a*10+*++s-'0';};
>          return a;
>      }
> 
>      int main(void) {
>          u64 a;
>          volatile u64 sum=0;
> 
>          for (int j=0; j<10000; ++j) {
>              for (int i=0; i<1000; ++i) {
>                  sum+=parseull(numbers[i]);
>              }
>          }
> 
>          printf("%llu\n",sum);
>      }
> 
> 

That's slower than the variants with intrinsics.

[toc] | [prev] | [next] | [standalone]

Page 1 of 4  [1] 2 3 4  Next page →

Back to top | Article view | comp.lang.c

csiph-web