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

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

How to div only once to get remainder and quotient?

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

Contents

  How to div only once to get remainder and quotient? Francis Assissi <invalid@invalid.invalid> - 2020-03-12 20:18 +0000
    Re: How to div only once to get remainder and quotient? Bart <bc@freeuk.com> - 2020-03-12 20:26 +0000
      Re: How to div only once to get remainder and quotient? Francis Assissi <invalid@invalid.invalid> - 2020-03-12 20:30 +0000
        Re: How to div only once to get remainder and quotient? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2020-03-12 20:40 -0700
      Re: How to div only once to get remainder and quotient? Lew Pitcher <lew.pitcher@digitalfreehold.ca> - 2020-03-12 16:38 -0400
        Re: How to div only once to get remainder and quotient? richard@cogsci.ed.ac.uk (Richard Tobin) - 2020-03-12 20:44 +0000
          Re: How to div only once to get remainder and quotient? Lew Pitcher <lew.pitcher@digitalfreehold.ca> - 2020-03-12 17:00 -0400
            Re: How to div only once to get remainder and quotient? richard@cogsci.ed.ac.uk (Richard Tobin) - 2020-03-13 09:35 +0000
              Re: How to div only once to get remainder and quotient? David Brown <david.brown@hesbynett.no> - 2020-03-13 11:12 +0100
        Re: How to div only once to get remainder and quotient? scott@slp53.sl.home (Scott Lurndal) - 2020-03-12 22:16 +0000
          Re: How to div only once to get remainder and quotient? Francis Assissi <invalid@invalid.invalid> - 2020-03-12 22:39 +0000
            Re: How to div only once to get remainder and quotient? Lew Pitcher <lew.pitcher@digitalfreehold.ca> - 2020-03-12 19:51 -0400
              Re: How to div only once to get remainder and quotient? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-03-13 00:47 +0000
                Re: How to div only once to get remainder and quotient? Lew Pitcher <lew.pitcher@digitalfreehold.ca> - 2020-03-12 23:02 -0400
                Re: How to div only once to get remainder and quotient? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2020-03-12 20:39 -0700
              Re: How to div only once to get remainder and quotient? scott@slp53.sl.home (Scott Lurndal) - 2020-03-13 15:00 +0000
              Re: How to div only once to get remainder and quotient? Spiros Bousbouras <spibou@gmail.com> - 2020-03-14 08:35 +0000
    Re: How to div only once to get remainder and quotient? jak <nospam@please.ty> - 2020-03-12 21:55 +0100
      Re: How to div only once to get remainder and quotient? Francis Assissi <invalid@invalid.invalid> - 2020-03-12 21:56 +0000
        Re: How to div only once to get remainder and quotient? jak <nospam@please.ty> - 2020-03-12 23:26 +0100
    Re: How to div only once to get remainder and quotient? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-03-12 21:11 +0000
      Re: How to div only once to get remainder and quotient? Francis Assissi <invalid@invalid.invalid> - 2020-03-12 21:57 +0000
      Re: How to div only once to get remainder and quotient? Bart <bc@freeuk.com> - 2020-03-12 22:23 +0000
        Re: How to div only once to get remainder and quotient? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-03-13 01:05 +0000
    Re: How to div only once to get remainder and quotient? David Brown <david.brown@hesbynett.no> - 2020-03-13 11:33 +0100
      Re: How to div only once to get remainder and quotient? Bart <bc@freeuk.com> - 2020-03-13 11:03 +0000
        Re: How to div only once to get remainder and quotient? David Brown <david.brown@hesbynett.no> - 2020-03-13 14:31 +0100
          Re: How to div only once to get remainder and quotient? Bart <bc@freeuk.com> - 2020-03-13 15:12 +0000
            Re: How to div only once to get remainder and quotient? David Brown <david.brown@hesbynett.no> - 2020-03-13 18:03 +0100
              Re: How to div only once to get remainder and quotient? Bart <bc@freeuk.com> - 2020-03-13 18:01 +0000
                Re: How to div only once to get remainder and quotient? David Brown <david.brown@hesbynett.no> - 2020-03-13 19:06 +0100
                  Re: How to div only once to get remainder and quotient? Bart <bc@freeuk.com> - 2020-03-13 19:12 +0000
        Re: How to div only once to get remainder and quotient? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-03-13 13:34 +0000
          Re: How to div only once to get remainder and quotient? Bart <bc@freeuk.com> - 2020-03-13 15:00 +0000
            Re: How to div only once to get remainder and quotient? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-03-13 20:34 +0000
              Re: How to div only once to get remainder and quotient? Bart <bc@freeuk.com> - 2020-03-13 21:41 +0000
                Re: How to div only once to get remainder and quotient? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-03-14 01:47 +0000
                  Re: How to div only once to get remainder and quotient? Bart <bc@freeuk.com> - 2020-03-14 12:24 +0000
                    Re: How to div only once to get remainder and quotient? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-03-14 16:35 +0000
                      Re: How to div only once to get remainder and quotient? Bart <bc@freeuk.com> - 2020-03-14 18:05 +0000
    Re: How to div only once to get remainder and quotient? already5chosen@yahoo.com - 2020-03-13 03:52 -0700
    Re: How to div only once to get remainder and quotient? Guillaume <message@bottle.org> - 2020-03-13 16:41 +0100
      Re: How to div only once to get remainder and quotient? Francis Assissi <invalid@invalid.invalid> - 2020-03-13 16:07 +0000
        Re: How to div only once to get remainder and quotient? David Brown <david.brown@hesbynett.no> - 2020-03-13 18:10 +0100
          Re: How to div only once to get remainder and quotient? Francis Assissi <invalid@invalid.invalid> - 2020-03-13 19:32 +0000
            Re: How to div only once to get remainder and quotient? James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-03-13 16:08 -0400
              Re: How to div only once to get remainder and quotient? Francis Assissi <invalid@invalid.invalid> - 2020-03-13 20:50 +0000
                Re: How to div only once to get remainder and quotient? jameskuyper@stellarscience.com - 2020-03-13 16:05 -0700
                  Re: How to div only once to get remainder and quotient? Francis Assissi <invalid@invalid.invalid> - 2020-03-13 23:42 +0000
                    Re: How to div only once to get remainder and quotient? James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-03-13 19:59 -0400
                      Re: How to div only once to get remainder and quotient? Francis Assissi <invalid@invalid.invalid> - 2020-03-14 00:07 +0000
                        Re: How to div only once to get remainder and quotient? James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-03-13 20:27 -0400
                          Re: How to div only once to get remainder and quotient? Francis Assissi <invalid@invalid.invalid> - 2020-03-14 01:37 +0000
                      Re: How to div only once to get remainder and quotient? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2020-04-02 07:45 -0700
                        Re: How to div only once to get remainder and quotient? James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-04-02 08:09 -0700
                        Re: How to div only once to get remainder and quotient? gazelle@shell.xmission.com (Kenny McCormack) - 2020-04-02 16:03 +0000
                          Re: How to div only once to get remainder and quotient? Öö Tiib <ootiib@hot.ee> - 2020-04-04 04:31 -0700
                            Invitations (Was: How to div only once to get remainder and quotient?) gazelle@shell.xmission.com (Kenny McCormack) - 2020-04-04 17:04 +0000
                              Re: Invitations (Was: How to div only once to get remainder and quotient?) Öö Tiib <ootiib@hot.ee> - 2020-04-07 00:10 -0700
        Re: How to div only once to get remainder and quotient? James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-03-13 14:30 -0400
          Re: How to div only once to get remainder and quotient? Francis Assissi <invalid@invalid.invalid> - 2020-03-13 20:54 +0000
            Re: How to div only once to get remainder and quotient? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-03-13 23:10 +0000
            Re: How to div only once to get remainder and quotient? James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-03-13 20:18 -0400
              Re: How to div only once to get remainder and quotient? Francis Assissi <invalid@invalid.invalid> - 2020-03-14 00:34 +0000
                Re: How to div only once to get remainder and quotient? Francis Assissi <invalid@invalid.invalid> - 2020-03-14 01:47 +0000
    Re: How to div only once to get remainder and quotient? Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2020-03-13 14:39 -0600
      Re: How to div only once to get remainder and quotient? felix@palmen-it.de (Felix Palmen) - 2020-03-13 22:10 +0100
        Re: How to div only once to get remainder and quotient? Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2020-03-13 16:26 -0600
        Re: How to div only once to get remainder and quotient? David Brown <david.brown@hesbynett.no> - 2020-03-14 16:41 +0100
          Re: How to div only once to get remainder and quotient? felix@palmen-it.de (Felix Palmen) - 2020-03-14 17:00 +0100
            Re: How to div only once to get remainder and quotient? David Brown <david.brown@hesbynett.no> - 2020-03-15 13:39 +0100
      Re: How to div only once to get remainder and quotient? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-03-13 23:07 +0000
        Re: How to div only once to get remainder and quotient? Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2020-03-14 12:13 -0600
    Re: How to div only once to get remainder and quotient? Bonita Montero <Bonita.Montero@gmail.com> - 2020-04-07 09:35 +0200

Page 2 of 4 — ← Prev page 1 [2] 3 4  Next page →

#150521

Francis Assissi <invalid@invalid.invalid> writes:

> The following code serves to convert a decimal number to binary,

The number is already in binary when you start work on it.  What your
code does is convert a binary number to a string of 0 and 1 characters.
This is not just word play.  Since the number is stored as a collection
of bits, you can convert to 0/1 character without doing and divisions at
all.

> but this conversion requires dividing twice: once to get quotient,
> another to get the remainder. Is there a function to get both in a
> single operation like it is possible with Assembly?

Yes: div declared in stdlib.h.

> #include <stdio.h>
> #include <stdlib.h>
> #include <string.h>
>
> #define LENGTH 32

Keeping your fingers crossed that that is enough!  One day you will
enhance the code to deal with, say, negative numbers and you might
forget to change this.  You can use sizeof and CHAR_BIT to calculate a
size that is big enough.

> int main(void)
> {
>         int number              = 1234567890;
>         char bin_string[LENGTH] = {0};

There's no need to set the array to all zeros.  You set is all
immediately below.

>         char *ptr               = bin_string + LENGTH - 1;
>
>         memset(bin_string, '0', LENGTH);

You can use sizeof bin_string if you want to avoid repeating LENGTH.

>         *ptr = '\0';
>         --ptr;
>         while(number > 0 && ptr > bin_string) {

This condition is wrong.  It prevents the very first position in
bin_string from being used, and you need all 32 positions just for
positive integers (31 zero/one bits and a nul at the end).

>                 *ptr = '0' + number % 2;
>                 number /= 2;

If you want to avoid division, use bit operations: number & 1 gives you
the bottom bit, and number >>= 1 shifts the bits to the right.  I can
safely suggest this because your code only deals with positive numbers.
To handle negative numbers you need to take more care.

But it is very likely that the compiler will replace you % and /
operators anyway.  These days, it is almost always better to write what
you mean as clearly as possible and let the compiler do its thing.

>                 --ptr;
>         }

Here you have an interesting condition you could test for.  One thing I
always do after a while loop is to ask "what do I know here?".  One
thing I know here is that either number == 0 or ptr <= bin_string.  If I
get here with number != 0 I know the buffer ran out of space.  Since you
put both tests in while condition, you presumably though that either of
them might stop the loop.  If so, you should probably take some action
here if number is not zero.

>         puts(bin_string);
>         exit(EXIT_SUCCESS);
> }

-- 
Ben.

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

#150525

Thanks for the review.

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

#150527

On 12/03/2020 21:11, Ben Bacarisse wrote:
> Francis Assissi <invalid@invalid.invalid> writes:
> 
>> The following code serves to convert a decimal number to binary,

(That statement didn't register at all with me. The question asked 
suggested this was the usual binary to decimal text conversion.)


>> #define LENGTH 32
> 
> Keeping your fingers crossed that that is enough!  One day you will
> enhance the code to deal with, say, negative numbers and you might
> forget to change this.  You can use sizeof and CHAR_BIT to calculate a
> size that is big enough.

For generating binary, the largest likely to be needed is 64 characters 
for 64-bit numbers. Plus one more for a terminating zero. Plus I think 
up to 15 more if separators, every 4 digits, are added into the output 
(a good idea with binary).

Plus two more if a prefix such as '0b' is added.

You might add one more for a sign, but I think that would be unusual for 
binary output (which I might also prefer with leading zeros).

In practise just make this temporary array 128 characters, or 256 if 
planning to work with 128-bit values.

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

#150533

Bart <bc@freeuk.com> writes:

> On 12/03/2020 21:11, Ben Bacarisse wrote:
>> Francis Assissi <invalid@invalid.invalid> writes:
<cut>
>>> #define LENGTH 32
>>
>> Keeping your fingers crossed that that is enough!  One day you will
>> enhance the code to deal with, say, negative numbers and you might
>> forget to change this.  You can use sizeof and CHAR_BIT to calculate a
>> size that is big enough.
>
> For generating binary, the largest likely to be needed is 64
> characters for 64-bit numbers. Plus one more for a terminating
> zero. Plus I think up to 15 more if separators, every 4 digits, are
> added into the output (a good idea with binary).
>
> Plus two more if a prefix such as '0b' is added.
>
> You might add one more for a sign, but I think that would be unusual
> for binary output (which I might also prefer with leading zeros).
>
> In practise just make this temporary array 128 characters, or 256 if
> planning to work with 128-bit values.

In practise I'd make the buffer the size it needs to be, with a nice
explanatory comment.

-- 
Ben.

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

#150540

On 12/03/2020 21:18, Francis Assissi wrote:
> The following code serves to convert a decimal number to binary,
> but this conversion requires dividing twice: once to get quotient,
> another to get the remainder. Is there a function to get both in a
> single operation like it is possible with Assembly?
> 

Prioritise clarity of code first.  Is it obvious what the code does, and
obvious that it is correct?  Here you have written the divisor twice.
If it can't possibly be anything else than 2, that's fine - if it could
be different, then perhaps it is better to make it a named constant.

When code is correct, you can start considering such micro-optimisations
for highest efficiency.  First, ask yourself if it is actually relevant.
 Here it clearly is not - the "puts" call with take thousands of times
longer than any division.  Then, if you are convinced greater efficiency
is important, start measuring the timings.  (In this case, you'll
quickly see that the division is not a bottleneck.)  Then, once you are
sure you have found the bottlenecks, you can start looking at optimisations.

To be able to micro-optimise something like this, you have to have a
good understanding of your compiler and its optimisations and code
generation (micro-optimising source code without having compiler
optimisation enabled is utterly pointless), and a reasonable
understanding of assembly and how the cpu works.  In the case of
division by 2, the assembly is of course negligible, with the "and" and
shift instructions being smaller and faster than any division.

In general, a good compiler will be far better at optimising code than
you are.  Any use of "div" is almost certainly worse than writing % and
/ individually, because if a combined assembly instruction were useful,
the compiler would use it, while in most cases it can optimise the
separate operators better.  Any use of "div" with a constant denominator
is /definitely/ wrong (assuming a normal compiler) - it is much less
clear in the code, and will usually greatly hinder optimisation.

Apart from writing "bin_string" three times instead of once, the code is
fine.


> #include <stdio.h>
> #include <stdlib.h>
> #include <string.h>
> 
> #define LENGTH 32
> 
> int main(void)
> {
>         int number              = 1234567890;
>         char bin_string[LENGTH] = {0};
>         char *ptr               = bin_string + LENGTH - 1;
> 
>         memset(bin_string, '0', LENGTH);
>         *ptr = '\0';
>         --ptr;
>         while(number > 0 && ptr > bin_string) {
>                 *ptr = '0' + number % 2;
>                 number /= 2;
>                 --ptr;
>         }
>         puts(bin_string);
>         exit(EXIT_SUCCESS);
> }
> 

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

#150544

On 13/03/2020 10:33, David Brown wrote:
> On 12/03/2020 21:18, Francis Assissi wrote:
>> The following code serves to convert a decimal number to binary,
>> but this conversion requires dividing twice: once to get quotient,
>> another to get the remainder. Is there a function to get both in a
>> single operation like it is possible with Assembly?
>>
> 
> Prioritise clarity of code first.  Is it obvious what the code does, and
> obvious that it is correct?  Here you have written the divisor twice.
> If it can't possibly be anything else than 2, that's fine - if it could
> be different, then perhaps it is better to make it a named constant.
> 
> When code is correct, you can start considering such micro-optimisations
> for highest efficiency.  First, ask yourself if it is actually relevant.
>   Here it clearly is not - the "puts" call with take thousands of times
> longer than any division.

If each result will always be written individually by printf or puts, 
that may be true. But the code might end up in a function that writes 
millions of binary strings to memory (maybe, later writing that to a 
file as one memoryblock).

The modified version below makes it possible to play around with it to 
see what can make a difference.

Even if it doesn't, or it always passed to puts/printf, such exercise 
can be good experience for when it does matter.

Here I would expect lldiv (which will do at least one actual DIV, rather 
than one SHIFT and one AND as is likely here) to slow it down. As would 
making the '2' into a parameter as then it would also need to do actual 
divides.

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

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

typedef unsigned long long int u64;

void strbin(u64 number, char* bin_string) {
         enum {LENGTH=64};
         char *ptr               = bin_string + LENGTH;

         memset(bin_string, '0', LENGTH);
         *ptr = '\0';
         --ptr;
         while(number > 0 && ptr > bin_string) {
                 *ptr = '0' + number % 2;
                 number /= 2;
                 --ptr;
         }
}

int main(void) {
     char str[128];

     for (int i=0; i<10000000; ++i)
         strbin(0b1011011101111011111011111101111111011111111, str);
     puts(str);
}

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

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

#150545

On 13/03/2020 12:03, Bart wrote:
> On 13/03/2020 10:33, David Brown wrote:
>> On 12/03/2020 21:18, Francis Assissi wrote:
>>> The following code serves to convert a decimal number to binary,
>>> but this conversion requires dividing twice: once to get quotient,
>>> another to get the remainder. Is there a function to get both in a
>>> single operation like it is possible with Assembly?
>>>
>>
>> Prioritise clarity of code first.  Is it obvious what the code does, and
>> obvious that it is correct?  Here you have written the divisor twice.
>> If it can't possibly be anything else than 2, that's fine - if it could
>> be different, then perhaps it is better to make it a named constant.
>>
>> When code is correct, you can start considering such micro-optimisations
>> for highest efficiency.  First, ask yourself if it is actually relevant.
>>   Here it clearly is not - the "puts" call with take thousands of times
>> longer than any division.
> 
> If each result will always be written individually by printf or puts,
> that may be true. But the code might end up in a function that writes
> millions of binary strings to memory (maybe, later writing that to a
> file as one memoryblock).

Please re-read what I wrote.  I did not say efficiency is irrelevant - I
said code clarity is much more important, and micro-efficiency should be
ignored unless you know it really is an issue.  In this code, it very
clearly is /not/ an issue.

> 
> The modified version below makes it possible to play around with it to
> see what can make a difference.

And you'll find that using "div" either makes no difference, or will
decrease performance.

> 
> Even if it doesn't, or it always passed to puts/printf, such exercise
> can be good experience for when it does matter.

Agreed.  Again, read what I wrote - don't faff around trying to find
small optimisations until you have measured the results and seen that it
makes a difference.  Re-arranging code into a form where efficiency can
be measured is an obvious part of that.

> 
> Here I would expect lldiv (which will do at least one actual DIV, rather
> than one SHIFT and one AND as is likely here) to slow it down. As would
> making the '2' into a parameter as then it would also need to do actual
> divides.
> 
Agreed.

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

#150549

On 13/03/2020 13:31, David Brown wrote:
> On 13/03/2020 12:03, Bart wrote:


>> If each result will always be written individually by printf or puts,
>> that may be true. But the code might end up in a function that writes
>> millions of binary strings to memory (maybe, later writing that to a
>> file as one memoryblock).
> 
> Please re-read what I wrote.  I did not say efficiency is irrelevant - I
> said code clarity is much more important, and micro-efficiency should be
> ignored unless you know it really is an issue.  In this code, it very
> clearly is /not/ an issue.

It seemed very likely to me that the puts was just there to test the 
output, enough that you can't say that the efficiency of such a routine 
'clearly' wasn't relevant.

I know from experience that conversion to decimal can cause some 
inefficency even without such direct output. Conversion to binary or hex 
is not as bad since it need not involve division, but we don't know here 
what will be important.

The code here could also be adapted by the OP to other bases (I tried it 
with base 3 to force a division).

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

#150552

On 13/03/2020 16:12, Bart wrote:
> On 13/03/2020 13:31, David Brown wrote:
>> On 13/03/2020 12:03, Bart wrote:
> 
> 
>>> If each result will always be written individually by printf or puts,
>>> that may be true. But the code might end up in a function that writes
>>> millions of binary strings to memory (maybe, later writing that to a
>>> file as one memoryblock).
>>
>> Please re-read what I wrote.  I did not say efficiency is irrelevant - I
>> said code clarity is much more important, and micro-efficiency should be
>> ignored unless you know it really is an issue.  In this code, it very
>> clearly is /not/ an issue.
> 
> It seemed very likely to me that the puts was just there to test the
> output, enough that you can't say that the efficiency of such a routine
> 'clearly' wasn't relevant.
> 

It seems equally likely that the primary purpose of turning an integer
into a string of 0 and 1 characters is to print it out somewhere (to a
terminal, file, etc.).

> I know from experience that conversion to decimal can cause some
> inefficency even without such direct output. Conversion to binary or hex
> is not as bad since it need not involve division, but we don't know here
> what will be important.

In the conversion itself, decimal is often more time-consuming because
you are dividing by 10, not a power of 2.  But you almost invariably
want to do something with the resulting string that is a great deal more
time-consuming than the conversion.

> 
> The code here could also be adapted by the OP to other bases (I tried it
> with base 3 to force a division).

Indeed.  Again, look at what I wrote in the first place.

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

#150554

On 13/03/2020 17:03, David Brown wrote:
> On 13/03/2020 16:12, Bart wrote:
>> On 13/03/2020 13:31, David Brown wrote:
>>> On 13/03/2020 12:03, Bart wrote:
>>
>>
>>>> If each result will always be written individually by printf or puts,
>>>> that may be true. But the code might end up in a function that writes
>>>> millions of binary strings to memory (maybe, later writing that to a
>>>> file as one memoryblock).
>>>
>>> Please re-read what I wrote.  I did not say efficiency is irrelevant - I
>>> said code clarity is much more important, and micro-efficiency should be
>>> ignored unless you know it really is an issue.  In this code, it very
>>> clearly is /not/ an issue.
>>
>> It seemed very likely to me that the puts was just there to test the
>> output, enough that you can't say that the efficiency of such a routine
>> 'clearly' wasn't relevant.
>>
> 
> It seems equally likely that the primary purpose of turning an integer
> into a string of 0 and 1 characters is to print it out somewhere (to a
> terminal, file, etc.).
...
> In the conversion itself, decimal is often more time-consuming because
> you are dividing by 10, not a power of 2.  But you almost invariably
> want to do something with the resulting string that is a great deal more
> time-consuming than the conversion.

I think the result of most such conversions will never be displayed.

Think of generating HLL source code, ASM source, CSV files, XML, 
listings files, log files, or just piping the output to another process, 
or directing it to a file.

So perhaps the most time-consuming thing might be turning it back into 
binary. Which usually involves multiplies rather than divides.

(Eg. gcc appears to work by generating .s files which are then processed 
by 'as'.)

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

#150555

On 13/03/2020 19:01, Bart wrote:
> On 13/03/2020 17:03, David Brown wrote:
>> On 13/03/2020 16:12, Bart wrote:
>>> On 13/03/2020 13:31, David Brown wrote:
>>>> On 13/03/2020 12:03, Bart wrote:
>>>
>>>
>>>>> If each result will always be written individually by printf or puts,
>>>>> that may be true. But the code might end up in a function that writes
>>>>> millions of binary strings to memory (maybe, later writing that to a
>>>>> file as one memoryblock).
>>>>
>>>> Please re-read what I wrote.  I did not say efficiency is irrelevant
>>>> - I
>>>> said code clarity is much more important, and micro-efficiency
>>>> should be
>>>> ignored unless you know it really is an issue.  In this code, it very
>>>> clearly is /not/ an issue.
>>>
>>> It seemed very likely to me that the puts was just there to test the
>>> output, enough that you can't say that the efficiency of such a routine
>>> 'clearly' wasn't relevant.
>>>
>>
>> It seems equally likely that the primary purpose of turning an integer
>> into a string of 0 and 1 characters is to print it out somewhere (to a
>> terminal, file, etc.).
> ...
>> In the conversion itself, decimal is often more time-consuming because
>> you are dividing by 10, not a power of 2.  But you almost invariably
>> want to do something with the resulting string that is a great deal more
>> time-consuming than the conversion.
> 
> I think the result of most such conversions will never be displayed.
> 
> Think of generating HLL source code, ASM source, CSV files, XML,
> listings files, log files, or just piping the output to another process,
> or directing it to a file.

It doesn't matter.  All of these will take many orders of magnitude more
processor cycles than a division, or the entire conversion to binary digits.

> 
> So perhaps the most time-consuming thing might be turning it back into
> binary. Which usually involves multiplies rather than divides.

Multiplication by powers of two is not time-consuming for a cpu.

> 
> (Eg. gcc appears to work by generating .s files which are then processed
> by 'as'.)

Yes.  And one of the reasons no one has made a big effort to change
that, is that it is such a minor part of the time taken for the
compilation process.  (Effort /is/ taken to have the temporary assembly
files kept in memory rather than written out as files to a disk.)

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

#150557

On 13/03/2020 18:06, David Brown wrote:
> On 13/03/2020 19:01, Bart wrote:

>> I think the result of most such conversions will never be displayed.
>>
>> Think of generating HLL source code, ASM source, CSV files, XML,
>> listings files, log files, or just piping the output to another process,
>> or directing it to a file.
> 
> It doesn't matter.  All of these will take many orders of magnitude more
> processor cycles than a division, or the entire conversion to binary digits.

No they don't. *Printing* results to a display might do, but as I said 
usually this doesn't happen.

Take this sequence of generated ASM code:

     mov       A0,   [Dframe-16]
     add       A0,   123
     mov       A2,   [Dframe-24]
     sub       A2,   456
     imul2     A0,   A2
     mov       [Dframe-8],   A0

I have a test that generates multiple repetitions of such code.

Generated numbers occur in 3 places: (a) the offsets; (b) the operands; 
(c) the register names.

Taking the binary->decimal calls that generate (a) and (b), and calling 
them twice, increases runtime by 10%. So they account for approx 10% of 
runtime.

Any savings won't be 10% because I still have to generate the numbers, 
but if you can find a faster way, it might save 5%. It doesn't sound 
much, but there might many such optimisations.

Now take (c), which are generated from a pre-generated 2D table of 
register index and size. This is an existing optimisation; if I take it 
out and do binary-decimal conversion each time to build the name, it 
slows it down by nearly 25%.


>> So perhaps the most time-consuming thing might be turning it back into
>> binary. Which usually involves multiplies rather than divides.
> 
> Multiplication by powers of two is not time-consuming for a cpu.

Sure, if you have a dedicated conversion for each number base. If are 
converting a string in base N into binary, then optimisation is not 
possible.


>>
>> (Eg. gcc appears to work by generating .s files which are then processed
>> by 'as'.)
> 
> Yes.  And one of the reasons no one has made a big effort to change
> that, is that it is such a minor part of the time taken for the
> compilation process.

Because gcc is slow anyway. My tools are faster and these details 
matter. My point however is that all those generated numbers are never 
printed out, only converted back to binary.

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

#150546

Bart <bc@freeuk.com> writes:

> void strbin(u64 number, char* bin_string) {
>         enum {LENGTH=64};
>         char *ptr               = bin_string + LENGTH;
>
>         memset(bin_string, '0', LENGTH);
>         *ptr = '\0';
>         --ptr;
>         while(number > 0 && ptr > bin_string) {
>                 *ptr = '0' + number % 2;
>                 number /= 2;
>                 --ptr;
>         }
> }

This is not a good way to write it.  Lots of posters are either
perpetuating the bug or saying "it's fine" when it isn't.

What's more, post-decrementing ptr introduces a subtle bug once the main
one (not being able to use the whole buffer) is fixed.

This is a C group -- we should try to post good C.  There have been
correct versions posted (at least I think they were fine) but this one
isn't.

> int main(void) {
>     char str[128];
>
>     for (int i=0; i<10000000; ++i)
>         strbin(0b1011011101111011111011111101111111011111111, str);

Try with -1.

>     puts(str);
> }

-- 
Ben.

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

#150548

On 13/03/2020 13:34, Ben Bacarisse wrote:
> Bart <bc@freeuk.com> writes:
> 
>> void strbin(u64 number, char* bin_string) {
>>          enum {LENGTH=64};
>>          char *ptr               = bin_string + LENGTH;
>>
>>          memset(bin_string, '0', LENGTH);
>>          *ptr = '\0';
>>          --ptr;
>>          while(number > 0 && ptr > bin_string) {
>>                  *ptr = '0' + number % 2;
>>                  number /= 2;
>>                  --ptr;
>>          }
>> }
> 
> This is not a good way to write it.  Lots of posters are either
> perpetuating the bug or saying "it's fine" when it isn't.

I wasn't trying to rewrite it, only adapt the same code so it could be 
used via a function. The tests I did were cursory so that the timings 
would be meaningful.


> What's more, post-decrementing ptr introduces a subtle bug once the main
> one (not being able to use the whole buffer) is fixed.
> 
> This is a C group -- we should try to post good C.  There have been
> correct versions posted (at least I think they were fine) but this one
> isn't.
> 
>> int main(void) {
>>      char str[128];
>>
>>      for (int i=0; i<10000000; ++i)
>>          strbin(0b1011011101111011111011111101111111011111111, str);
> 
> Try with -1.

Yes, it doesn't process the top bit. Using LENGTH=8 and submitting 
0b11111111 will show the same. Maybe changing the second > to >= will 
fix it, but I'm not interested here in changing the code (which I would 
write totally differently anyway).

However, the original was intended to deal with 32-bit integers, and I 
think the above code does that.

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

#150560

Bart <bc@freeuk.com> writes:

> On 13/03/2020 13:34, Ben Bacarisse wrote:
>> Bart <bc@freeuk.com> writes:
>>
>>> void strbin(u64 number, char* bin_string) {
>>>          enum {LENGTH=64};
>>>          char *ptr               = bin_string + LENGTH;
>>>
>>>          memset(bin_string, '0', LENGTH);
>>>          *ptr = '\0';
>>>          --ptr;
>>>          while(number > 0 && ptr > bin_string) {
>>>                  *ptr = '0' + number % 2;
>>>                  number /= 2;
>>>                  --ptr;
>>>          }
>>> }
>>
>> This is not a good way to write it.  Lots of posters are either
>> perpetuating the bug or saying "it's fine" when it isn't.
>
> I wasn't trying to rewrite it, only adapt the same code so it could be
> used via a function. The tests I did were cursory so that the timings
> would be meaningful.

You changed the code.  You changed the type is appears to handle, the
minimum length buffer to use, the way the length is specified and the
initial position that gets written to.  You even changed the bug in that
the same test is now wrong for slightly different reasons.  But you did
not remove the bug.  That seems odd.

>> What's more, post-decrementing ptr introduces a subtle bug once the main
>> one (not being able to use the whole buffer) is fixed.
>>
>> This is a C group -- we should try to post good C.  There have been
>> correct versions posted (at least I think they were fine) but this one
>> isn't.
>>
>>> int main(void) {
>>>      char str[128];
>>>
>>>      for (int i=0; i<10000000; ++i)
>>>          strbin(0b1011011101111011111011111101111111011111111, str);
>>
>> Try with -1.
>
> Yes, it doesn't process the top bit. Using LENGTH=8 and submitting
> 0b11111111 will show the same. Maybe changing the second > to >= will
> fix it, but I'm not interested here in changing the code (which I
> would write totally differently anyway).

Or maybe it won't.  Or maybe it will introduce another bug?  Wouldn't it
be better to show how to write clear, correct C?

(I didn't do a re-write because I thought the OP was learning and that
giving a code review would be more helpful.)

> However, the original was intended to deal with 32-bit integers, and I
> think the above code does that.

I don't know in what sense the above codes "deal[s] with 32-bit
integers".

-- 
Ben.

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

#150565

On 13/03/2020 20:34, Ben Bacarisse wrote:
> Bart <bc@freeuk.com> writes:

> 
> You changed the code.  You changed the type is appears to handle, the
> minimum length buffer to use, the way the length is specified and the
> initial position that gets written to.  You even changed the bug in that
> the same test is now wrong for slightly different reasons.  But you did
> not remove the bug.  That seems odd.

I wasn't looking for bugs. I changed it into a function, and where a nul 
was written as it belongs outside the 32 characters of the result.

(Maybe the original was only intended to process the bottom 31 bits?)

> Or maybe it won't.  Or maybe it will introduce another bug?  Wouldn't it
> be better to show how to write clear, correct C?
> 
> (I didn't do a re-write because I thought the OP was learning and that
> giving a code review would be more helpful.)
> 
>> However, the original was intended to deal with 32-bit integers, and I
>> think the above code does that.
> 
> I don't know in what sense the above codes "deal[s] with 32-bit
> integers".
> 

I thought that using LENGTH=32 would do it, but it means that >/>= bug 
manifests itself at bit 31 rather than 63.

If I write it according to a similar spec, then it might look like this:

void strbin(u64 a, char* dest) {
     enum {bits = 64};
     u64 m = 0x8000000000000000;

     for (int i=0; i<bits; ++i) {
         if (a & m) {
             dest[i]='1';
         } else {
             dest[i]='0';
         }
         m >>= 1;
     }
     dest[bits]=0;
}

Parameters are not modified. Destination is built up in ascending order. 
It doesn't do anything clever.

Such a routine is always a little fiddly because you are traversing the 
string from char 0 to 63 while the integer is scanned from bit 63 to 0, 
or vice versa.

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

#150578

Bart <bc@freeuk.com> writes:

> On 13/03/2020 20:34, Ben Bacarisse wrote:
>> Bart <bc@freeuk.com> writes:
>
>>
>> You changed the code.  You changed the type is appears to handle, the
>> minimum length buffer to use, the way the length is specified and the
>> initial position that gets written to.  You even changed the bug in that
>> the same test is now wrong for slightly different reasons.  But you did
>> not remove the bug.  That seems odd.
>
> I wasn't looking for bugs. I changed it into a function, and where a
> nul was written as it belongs outside the 32 characters of the result.
>
> (Maybe the original was only intended to process the bottom 31 bits?)

Quite probably, but it also had the same bug (but for slightly different
reasons), even when processing only 31 bits.

> If I write it according to a similar spec, then ...

How about:

  static void str_to_bin_aux(uint64_t n, char *dest, int wd)
  {
       if (wd == 1)
            *dest = "01"[n & 1];
       else {
            wd /= 2;
            str_to_bin_aux(n,       dest+wd, wd);
            str_to_bin_aux(n >> wd, dest,    wd);
       }
  }
   
  char *str_to_bin(uint64_t n, char *dest)
  {
       enum { bits = sizeof n * CHAR_BIT };
       str_to_bin_aux(n, dest, bits);
       dest[bits] = 0;
       return dest;
  }

:-)

(By the way, names starting "str" and a lower case letter are reserved
for future use in string.h, hence my choice of "str_".)

-- 
Ben.

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

#150582

On 14/03/2020 01:47, Ben Bacarisse wrote:
> Bart <bc@freeuk.com> writes:
> 
>> On 13/03/2020 20:34, Ben Bacarisse wrote:
>>> Bart <bc@freeuk.com> writes:
>>
>>>
>>> You changed the code.  You changed the type is appears to handle, the
>>> minimum length buffer to use, the way the length is specified and the
>>> initial position that gets written to.  You even changed the bug in that
>>> the same test is now wrong for slightly different reasons.  But you did
>>> not remove the bug.  That seems odd.
>>
>> I wasn't looking for bugs. I changed it into a function, and where a
>> nul was written as it belongs outside the 32 characters of the result.
>>
>> (Maybe the original was only intended to process the bottom 31 bits?)
> 
> Quite probably, but it also had the same bug (but for slightly different
> reasons), even when processing only 31 bits.
> 
>> If I write it according to a similar spec, then ...
> 
> How about:
> 
>    static void str_to_bin_aux(uint64_t n, char *dest, int wd)
>    {
>         if (wd == 1)
>              *dest = "01"[n & 1];
>         else {
>              wd /= 2;
>              str_to_bin_aux(n,       dest+wd, wd);
>              str_to_bin_aux(n >> wd, dest,    wd);
>         }
>    }
>     
>    char *str_to_bin(uint64_t n, char *dest)
>    {
>         enum { bits = sizeof n * CHAR_BIT };
>         str_to_bin_aux(n, dest, bits);
>         dest[bits] = 0;
>         return dest;
>    }
> 
> :-)
> 
> (By the way, names starting "str" and a lower case letter are reserved
> for future use in string.h, hence my choice of "str_".)
> 

Ah yes, the recursive solution. I felt obliged to put together my own, 
but it took ages to get it right and my confidence in it is not as great 
as with my iterative one. Not sure about UB either (eg. left-shifting by 0):

   void rstrbin(u64 a, char *dest, int bits) {
       if (bits) {
           if (a & (1LL<<(bits-1))) {
               *dest='1';
           } else {
               *dest='0';
           }
           rstrbin(a, dest+1, bits-1);
       } else {
           *dest=0;
       }
   }

This is a one-function version, requiring an extra parameter, but I 
believe this is a useful addition to the spec (so you can display 8, 16, 
32 or 64-bit wide numbers, or even 24 bits).

Both recursive versions are slower than the iterative ones under gcc 
-O3, but mine seemed double the speed of yours using bits=64 (and will 
be faster with fewer bits). With bcc/tcc mine was 2.5 times as fast, 
when calling it 10M lines.

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

#150585

Bart <bc@freeuk.com> writes:

> On 14/03/2020 01:47, Ben Bacarisse wrote:
<cut>
>> How about:
>>
>>    static void str_to_bin_aux(uint64_t n, char *dest, int wd)
>>    {
>>         if (wd == 1)
>>              *dest = "01"[n & 1];
>>         else {
>>              wd /= 2;
>>              str_to_bin_aux(n,       dest+wd, wd);
>>              str_to_bin_aux(n >> wd, dest,    wd);
>>         }
>>    }
>>        char *str_to_bin(uint64_t n, char *dest)
>>    {
>>         enum { bits = sizeof n * CHAR_BIT };
>>         str_to_bin_aux(n, dest, bits);
>>         dest[bits] = 0;
>>         return dest;
>>    }
>>
>> :-)
>>
>> (By the way, names starting "str" and a lower case letter are reserved
>> for future use in string.h, hence my choice of "str_".)
>>
>
> Ah yes, the recursive solution. I felt obliged to put together my own,
> but it took ages to get it right and my confidence in it is not as
> great as with my iterative one. Not sure about UB either
> (eg. left-shifting by 0):

That's fine.

>   void rstrbin(u64 a, char *dest, int bits) {
>       if (bits) {
>           if (a & (1LL<<(bits-1))) {
>               *dest='1';
>           } else {
>               *dest='0';
>           }
>           rstrbin(a, dest+1, bits-1);
>       } else {
>           *dest=0;
>       }
>   }
>
> This is a one-function version, requiring an extra parameter, but I
> believe this is a useful addition to the spec (so you can display 8,
> 16, 32 or 64-bit wide numbers, or even 24 bits).
>
> Both recursive versions are slower than the iterative ones under gcc
> -O3, but mine seemed double the speed of yours using bits=64 (and will
> be faster with fewer bits). With bcc/tcc mine was 2.5 times as fast,
> when calling it 10M lines.

I wonder if gcc turned your one-sided recursion into a loop.  My doubly
recursive version had a smiley for a reason!

-- 
Ben.

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

#150586

On 14/03/2020 16:35, Ben Bacarisse wrote:
> Bart <bc@freeuk.com> writes:
> 
>> On 14/03/2020 01:47, Ben Bacarisse wrote:
> <cut>
>>> How about:
>>>
>>>     static void str_to_bin_aux(uint64_t n, char *dest, int wd)
>>>     {
>>>          if (wd == 1)
>>>               *dest = "01"[n & 1];
>>>          else {
>>>               wd /= 2;
>>>               str_to_bin_aux(n,       dest+wd, wd);
>>>               str_to_bin_aux(n >> wd, dest,    wd);
>>>          }
>>>     }
>>>         char *str_to_bin(uint64_t n, char *dest)
>>>     {
>>>          enum { bits = sizeof n * CHAR_BIT };
>>>          str_to_bin_aux(n, dest, bits);
>>>          dest[bits] = 0;
>>>          return dest;
>>>     }
>>>
>>> :-)

>> Both recursive versions are slower than the iterative ones under gcc
>> -O3, but mine seemed double the speed of yours

> 
> I wonder if gcc turned your one-sided recursion into a loop.  My doubly
> recursive version had a smiley for a reason!

Yours seemed to take a complicated approach, but I didn't look at it in 
detail.

Now I can see it keeps dividing the task in half, and applying the 
function to each half, until it gets to a single bit.

I know how long that would have taken me to get it right...

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

Page 2 of 4 — ← Prev page 1 [2] 3 4  Next page →

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

csiph-web