Author Topic: number->string without division or multiplication  (Read 3516 times)

Offline OS923

  • Platinum Member (500+ Posts)
  • *****
  • Posts: 508
number->string without division or multiplication
« on: June 08, 2018, 06:53:39 AM »
What's the fastest algorithm to convert a binary number into a decimal number?

For SInt32 or smaller numbers I use NumToString from NumberFormatting. Otherwise I use the div/mod method.

It should be possible with comparisons and subtractions. But in which order?

For example.
Code: [Select]
if n>=2000000000 then
    Append "2"
    n-=2000000000
elsif n>=1000000000 then
    Append "1"
    n-=1000000000
else
    and so on.

Offline IIO

  • Platinum Member (500+ Posts)
  • *****
  • Posts: 2255
  • new to the forums
Re: number->string without division or multiplication
« Reply #1 on: June 08, 2018, 09:06:59 AM »
or set up an array somewhere which already contains all required multiples of 2.
"It is true that the "pre-emptive multitasking" advantage present in OS X can be illustrated by downloading CD-ROM ISOs and rendering chaos theory formulas while simultaneously instant messaging and posting on FaceBook what you ate... but in reality, what did you create?"
- DieHard, random forum troll at macos9lives.com

Offline Naiw

  • Veteran Member (100+ Posts)
  • ****
  • Posts: 116
  • new to the forums
Re: number->string without division or multiplication
« Reply #2 on: June 10, 2018, 04:05:54 PM »
There is no such thing as the fastest way, it depends completely on architecture.

But I would guess something like this is probably among the fastest on most cpus...

Code: [Select]
int main()
{
    unsigned long value = 0;
    char binary_string[] = "11111010000";
   
    unsigned long length = sizeof(binary_string)-1;
    unsigned long mask[] = {0, 0xffffffff};
   
    for(int s=length;s>0;s--) {
        int bit = s-1; // We're zero indexed- adjust
        value += (1<<bit) & mask[binary_string[length-bit-1]-48]; // Need to offset with the termination byte too... finally remove the ascii value of zero to map this to our bitmask table.
    }
    printf("Decimal value for %s is %lu\n",binary_string, value);
    return 0;
}

Now this particular example is written around a binary number in string format... because I misread the original post...

Also note that the loop is backwards intentionally- because while compilers may sometimes figure this out on their own, they don't always do, and pretty much all processors has loop conditions that are significantly faster if they compare with zero.
PowerPC for example even have a special counter register designed for this purpose (CTR - ie. the loop turns into a single bdnz; decrement CTR and branch if not zero) that is way faster than compare&jump looping (cmpwi / bne).

---

Actually are you talking binary here or BCD? Cause after reading your other post I'm highly suspecting you're intending to ask about how to most efficiently encode/decode BCD encoded values?
« Last Edit: June 10, 2018, 04:22:40 PM by Naiw »

Offline OS923

  • Platinum Member (500+ Posts)
  • *****
  • Posts: 508
Re: number->string without division or multiplication
« Reply #3 on: June 11, 2018, 08:50:35 AM »
When I say binary number then I mean something of the type SInt8, SInt16, SInt32, SInt64, UInt8, UInt16, UInt32, or UInt64.

So I search the fastest solution for:
Code: [Select]
void Convert(SInt8 n,StringPtr s);
void Convert(SInt16 n,StringPtr s);
void Convert(SInt32 n,StringPtr s);
void Convert(SInt64 n,StringPtr s);
void Convert(UInt8 n,StringPtr s);
void Convert(UInt16 n,StringPtr s);
void Convert(UInt32 n,StringPtr s);
void Convert(UInt64 n,StringPtr s);

Offline Naiw

  • Veteran Member (100+ Posts)
  • ****
  • Posts: 116
  • new to the forums
Re: number->string without division or multiplication
« Reply #4 on: June 11, 2018, 09:41:40 AM »
When I say binary number then I mean something of the type SInt8, SInt16, SInt32, SInt64, UInt8, UInt16, UInt32, or UInt64.

So I search the fastest solution for:
Code: [Select]
void Convert(SInt8 n,StringPtr s);
void Convert(SInt16 n,StringPtr s);
void Convert(SInt32 n,StringPtr s);
void Convert(SInt64 n,StringPtr s);
void Convert(UInt8 n,StringPtr s);
void Convert(UInt16 n,StringPtr s);
void Convert(UInt32 n,StringPtr s);
void Convert(UInt64 n,StringPtr s);

Well I don't know what Covert(type n, StringPtr s); does. it's not a standard call...

So I guess you're talking about parsing values then?

Offline OS923

  • Platinum Member (500+ Posts)
  • *****
  • Posts: 508
Re: number->string without division or multiplication
« Reply #5 on: June 15, 2018, 09:16:40 AM »
I tried a method without division or multiplication but it was a bit too slow.

I found a better solution. I treat numbers as base 100000 instead of base 10. This divides the number of divisions and multiplications by 5. This requires a table of 500000 bytes.

This is now part of OS 9.3.

Offline Naiw

  • Veteran Member (100+ Posts)
  • ****
  • Posts: 116
  • new to the forums
Re: number->string without division or multiplication
« Reply #6 on: June 18, 2018, 07:02:21 AM »
I believe this should be slightly faster...

Code: [Select]
unsigned int conv2(char *s)
{
  unsigned register int n = 0;
  do
  {
    n=(n<<3)+(n<<1)+(*s&0xf);
  } while(*++s);
  return n;
}

Offline OS923

  • Platinum Member (500+ Posts)
  • *****
  • Posts: 508
Re: number->string without division or multiplication
« Reply #7 on: June 18, 2018, 07:08:20 AM »
I'll try it, but in my experience, bit shifts and bit fields are slow.

Offline Naiw

  • Veteran Member (100+ Posts)
  • ****
  • Posts: 116
  • new to the forums
Re: number->string without division or multiplication
« Reply #8 on: June 18, 2018, 02:22:03 PM »
I'll try it, but in my experience, bit shifts and bit fields are slow.

Bit shifts are only slow on interpreters.

On physical hardware they're always the fastest or as fast as the alternatives.

In reality they're often faster as all other operands are implemented as shifts and combinational bitwise logic in a CPU.

For example masking the character with 0xF instead of subtracting 48 might not be faster on all machines but there shouldn't be a single instance where its slower.
It doesn't set any condition bits and in some it might event fuse into a shift with mask instruction (when used in this context).

Offline Naiw

  • Veteran Member (100+ Posts)
  • ****
  • Posts: 116
  • new to the forums
Re: number->string without division or multiplication
« Reply #9 on: June 19, 2018, 04:04:57 PM »
Regarding bit operands vs mathematic operands.

Now this isn't entierly representative as this is run through an ardurino- but just an example how much of a difference replacing totally unnecessary mathematics with bitfiddeling instead can do.

The first example is an implementation of bit angle modulation (a bit similar to PWM) that I used to drive 30 RGB diodes out of a single (software) UART on an ardurino- it's then fed through shift registers and the BAM allowed me to control the brightness of each individal LED.

So the first version- naively implemented using just pure (fixed point) mathematics

<a href="http://www.youtube.com/watch?v=zaTh_KaMZ1Q" target="_blank">http://www.youtube.com/watch?v=zaTh_KaMZ1Q</a>

When I had this working I started optimising it and rewrote it to using bit arithmetic only. And the result was the following- which is the exact same program.

<a href="http://www.youtube.com/watch?v=whKo9zpBqLE" target="_blank">http://www.youtube.com/watch?v=whKo9zpBqLE</a>

I think it demonstrates quite clearly how much of a difference, and this was just low hanging fruit.

Offline IIO

  • Platinum Member (500+ Posts)
  • *****
  • Posts: 2255
  • new to the forums
Re: number->string without division or multiplication
« Reply #10 on: June 19, 2018, 05:04:55 PM »
thatīs not fair. you have raised the voltage in video II from 12V to 450V.
"It is true that the "pre-emptive multitasking" advantage present in OS X can be illustrated by downloading CD-ROM ISOs and rendering chaos theory formulas while simultaneously instant messaging and posting on FaceBook what you ate... but in reality, what did you create?"
- DieHard, random forum troll at macos9lives.com

Offline Naiw

  • Veteran Member (100+ Posts)
  • ****
  • Posts: 116
  • new to the forums
Re: number->string without division or multiplication
« Reply #11 on: June 20, 2018, 01:39:30 PM »
thatīs not fair. you have raised the voltage in video II from 12V to 450V.

Hush don't reveal the secret sauce 😜

Offline OS923

  • Platinum Member (500+ Posts)
  • *****
  • Posts: 508
Re: number->string without division or multiplication
« Reply #12 on: June 25, 2018, 03:41:32 AM »
Your logic is correct for processors which can do only one thing at a time.

The problem with your bitshifts is that the processor has to wait for every calculation to complete before it can do the following calculation.

Your algorithm with bitshifts does essentially this: n=(((1*10)+2)*10+3)*10+4

If I write it like this: n=1*1000+2*100+3*10+4 then the processor can do several calculations at the same time because the order doesn't matter.

Both algorithms do 3 multiplications and 3 additions, but the second is faster.

Signed integers are faster too: n=1*1000L+2*100L+3*10L+4

And the "optimized" version is slower.

The first test that I measured calculates 100000 times the longest value.

The second test that I measured calculates 100000 times the longest value and 100000 times the shortest value.


Offline Naiw

  • Veteran Member (100+ Posts)
  • ****
  • Posts: 116
  • new to the forums
Re: number->string without division or multiplication
« Reply #13 on: June 25, 2018, 10:38:43 PM »
Your logic is correct for processors which can do only one thing at a time.

The problem with your bitshifts is that the processor has to wait for every calculation to complete before it can do the following calculation.

Your algorithm with bitshifts does essentially this: n=(((1*10)+2)*10+3)*10+4

If I write it like this: n=1*1000+2*100+3*10+4 then the processor can do several calculations at the same time because the order doesn't matter.

Both algorithms do 3 multiplications and 3 additions, but the second is faster.

Signed integers are faster too: n=1*1000L+2*100L+3*10L+4

And the "optimized" version is slower.

The first test that I measured calculates 100000 times the longest value.

The second test that I measured calculates 100000 times the longest value and 100000 times the shortest value.

Yes your theory would make sense if shifts were not a one cycle operation, you are right however that a multiplication can be masked by the pipelining on some CPUs as it could theoretically be performed in parallel- just as you describe.

May I ask what CPU you are targeting in this particular example?
Or even better if you mind share your benchmark setup, I find this quite interesting considering I did benchmark the algorithm on 3 architectures (x86, MIPS, ARM) before I confidently submit my post here.

Offline OS923

  • Platinum Member (500+ Posts)
  • *****
  • Posts: 508
Re: number->string without division or multiplication
« Reply #14 on: June 27, 2018, 02:36:19 AM »
Power Macintosh G4 1.25 DP (MDD) = 1.25 GHz PowerPC 7455 (G4)x2