Author Topic: string->number without multiplication  (Read 581 times)

Offline OS923

  • Gold Member
  • *****
  • Posts: 305
string->number without multiplication
« on: June 08, 2018, 07:00:54 AM »
What's the fastest algorithm to convert a decimal number into a binary number?

Normally I use something like
Code: [Select]
n*=10;n+=s[i]-48;
It should be possible with comparisons and additions. But in which order?

For example.
Code: [Select]
s="\p123456789"
t=reverse(s)
switch (t[1])
    case "9": d+=9
and so on
switch (t[2])
    case "9": d+=90
and so on

Offline IIO

  • Platinum Member
  • *****
  • Posts: 2012
  • new to the forums
Re: string->number without multiplication
« Reply #1 on: June 08, 2018, 09:04:25 AM »
What's the fastest algorithm to convert a decimal number into a binary number?

Normally I use something like
Code: [Select]
n*=10;n+=s[i]-48;
It should be possible with comparisons and additions. But in which order?

the most generalized method i can think of is a series:

assuming input is a LONG with no sign, i.e. 0-2147483647)

for the LSB: input %2

for all following bits: (input / 2 - (previously calulated bit*) / 2 )

*) or actually not bit, but digit or number, because this also works for tertiary, quartiery conversion and so on.

but depending on your language you might be able to avoid arithmetics and use some form of bitwise operation. for examplee if you only need to print the bits, you can just read the bits out of the "decimal number", which, as you know, doesnt exist anyway in that form. ;)

"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

  • Consistant Contributor
  • ***
  • Posts: 86
  • new to the forums
Re: string->number without multiplication
« Reply #2 on: June 10, 2018, 04:21:20 PM »
Actually are we talking binary numbers or BCD?....

Offline IIO

  • Platinum Member
  • *****
  • Posts: 2012
  • new to the forums
Re: string->number without multiplication
« Reply #3 on: June 11, 2018, 08:38:09 AM »
in the other thread he was talking about a "string", but i think the arithmetics (or other possible ways hot to solve the problem) wont differ much f rom a case where an array of 0 and 1 is the desried inout/output. :)
"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 OS923

  • Gold Member
  • *****
  • Posts: 305
Re: string->number without multiplication
« Reply #4 on: June 11, 2018, 08:46:00 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]
bool Convert(ConstStringPtr s,SInt8 &n);
bool Convert(ConstStringPtr s,SInt16 &n);
bool Convert(ConstStringPtr s,SInt32 &n);
bool Convert(ConstStringPtr s,SInt64 &n);
bool Convert(ConstStringPtr s,UInt8 &n);
bool Convert(ConstStringPtr s,UInt16 &n);
bool Convert(ConstStringPtr s,UInt32 &n);
bool Convert(ConstStringPtr s,UInt64 &n);

Offline Naiw

  • Consistant Contributor
  • ***
  • Posts: 86
  • new to the forums
Re: string->number without multiplication
« Reply #5 on: June 11, 2018, 09:47:59 AM »
in the other thread he was talking about a "string", but i think the arithmetics (or other possible ways hot to solve the problem) wont differ much f rom a case where an array of 0 and 1 is the desried inout/output. :)

Yeah I don't know what he's talking about really, but yes you're right the algorithm will look fairly similar either way.

But then again I ponder if it's what I suspect now... it's part of the stdlib- atoi / itoa(or sprintf on compilers that lacks itoa) and none of the stdlib implementations are "bad".

However I ponder if there is a need to optimise this further- it feels like the optimisation efforts are spent in the wrong area, a good algorithm doesn't convert between types at a time critical point as that's always something that costs and doesn't really give any benefit- the data is the same but stored in a different format.

---

Additionally yes the first example makes sense... somewhat if it's equivalent to atoi.

Just another thing- comparisions and branches is something you really don't want in time critical code, especially not on a superscalar CPU as a branch prediction miss or pipeline stall costs way way way way more than an unnecessary calculation, in fact unnecessary calculations are often free.

Also some other fundamental rules- especially applying to PowerPC.

An addition or subtraction is about 1 cycle.
A multiplication is around 5 - 8 cycles.
A division is around 35 cycles.
 
If you can use shifts instead of divisions or multiplications that will always be faster... a shift is 1 cycle (the PowerPC has a barrel shifter), it also has extremely useful shift and mask instructions.

For fixed point or integer values shift as much as possible, there's not a single architecture that is faster to calculate than shift.

If you really have to use (if using floating point forexample) multiplication or division it's faster (and if you use Altivec you have to- as it don't support division) to precompute (with the preprocessor in the best case) the divisor as a percentage and use multiplication instead.
Ie. res = number/35 is equivalent to #define DIVIDE_BY_THIRTYFIVE  (1.0/35.0)  res = number*DIVIDE_BY_THIRTYFIVE;

« Last Edit: June 11, 2018, 10:00:40 AM by Naiw »

Offline IIO

  • Platinum Member
  • *****
  • Posts: 2012
  • new to the forums
Re: string->number without multiplication
« Reply #6 on: June 11, 2018, 09:57:05 AM »
while the data type (or even its length) might not matter, the type of conversion can differ a lot for CPU.

i dont know his programmming langauge at all, but i bet that sprintf consumes far more than arithmetics or epxr based, and a possible bitwise processing solution is the best.
"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

  • Consistant Contributor
  • ***
  • Posts: 86
  • new to the forums
Re: string->number without multiplication
« Reply #7 on: June 11, 2018, 10:11:55 AM »
while the data type (or even its length) might not matter, the type of conversion can differ a lot for CPU.

i dont know his programmming langauge at all, but i bet that sprintf consumes far more than arithmetics or epxr based, and a possible bitwise processing solution is the best.

Why would the type conversion differ a lot? The fact something is signed or unsigned just tells the compiler what assembly instructions to use when operating on the data (if it should regard MSB as a negative sign or not).

sprintf has indeed some higher overhead than itoa- as it has to go through and parse the format string- but that's basically one iteration in a loop then it jumps directly to the conversion routine.

Offline IIO

  • Platinum Member
  • *****
  • Posts: 2012
  • new to the forums
Re: string->number without multiplication
« Reply #8 on: June 11, 2018, 10:34:04 AM »
something like printf or regexp works on a different level and has (depending on the enviroment) an overhard of mabye 10 or 50 times compared to multiplication/addition/modulus/...

of course, if you only need a certain type of data, it might (in some languages) be enough to change the "header" (or whatever it is. this will be needing less CPU than a radix conversion of a 32 bit int (with output format 32 bit int, or, for longer numbers, an array of SHORT or ASCI or whatever to store the 0 and 1 in.)
"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

  • Consistant Contributor
  • ***
  • Posts: 86
  • new to the forums
Re: string->number without multiplication
« Reply #9 on: June 13, 2018, 02:16:36 PM »
something like printf or regexp works on a different level and has (depending on the enviroment) an overhard of mabye 10 or 50 times compared to multiplication/addition/modulus/...

of course, if you only need a certain type of data, it might (in some languages) be enough to change the "header" (or whatever it is. this will be needing less CPU than a radix conversion of a 32 bit int (with output format 32 bit int, or, for longer numbers, an array of SHORT or ASCI or whatever to store the 0 and 1 in.)

Sprintf/printf isnít remotely similar to regexp, itís a very simple parser that advances the format string, if you claim otherwise you clearly havenít looked into the implementation of either.

Offline IIO

  • Platinum Member
  • *****
  • Posts: 2012
  • new to the forums
Re: string->number without multiplication
« Reply #10 on: June 13, 2018, 03:08:21 PM »
well, this isnt what he asked (i think we hijacked the thread by now), but there are generally two different approches/applictions.

if you have a LONG, then do a radix conversion, so that you will end up with 31 or 32 numbers, ech of type LONG, too, tht involves al lto of mth aas described above.

the other thing is to only change the type of something. of something which is displayed or "printed" as a 32 bit number and "converted" to binary "type". this does not need much CPU, because, well, it has been the same binary data before, it is only caalled differently in order to print it as something different. just like ... atoi. :)
"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 OS923

  • Gold Member
  • *****
  • Posts: 305
Re: string->number without multiplication
« Reply #11 on: June 15, 2018, 09:11:18 AM »
I found a better solution. I treat numbers as base 100 instead of base 10. This divides the number of multiplications by 2.

Another improvement is to avoid multiplication by zero. This is the usual algorithm:
Code: [Select]
n=0;
while (*s)
    {
    n*=10;
    n+=static_cast<char>(*s-48);
    s++;
    }
This starts with multiplying zero by 10, which is lost time. if (n) n*=10; is faster than n*=10; because the time that you win by eliminating one multiplication is longer than the time that you lose with several comparisons.

Offline OS923

  • Gold Member
  • *****
  • Posts: 305
Re: string->number without multiplication
« Reply #12 on: June 18, 2018, 07:06:43 AM »
This is an alternative improvement of the usual algorithm:

Code: [Select]
#define consume() n+=*s++;n-=48
n=0;
if (!*s) return;
consume();
while (*s)
    {
n*=10;
    consume();
    }
This saves 1 multiplication with only 1 extra comparison.