string->number without multiplication

[OS923]

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

[IIO]

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.

[Naiw]

Actually are we talking binary numbers or BCD?....

[IIO]

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.

[OS923]

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);


[Naiw]

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;

[IIO]

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.

[Naiw]

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.

[IIO]

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

[Naiw]

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.

[IIO]

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.

[OS923]

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.

[OS923]

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.

[OS923]

Apple's function does a bit more than I thought. It checks leading spaces and zeroes and this makes a difference of 25%.

There's something that they don't tell you in the documentation: + or - has to be the first character if you use it.

Code: [Select]

#include <NumberFormatting.h>

#include <iostream>

using namespace std;

int main()
{
    SInt32 x;

    ::StringToNum("\p00123",
                  &x);
    cout << x << endl;
    ::StringToNum("\p+00123",
                  &x);
    cout << x << endl;
    ::StringToNum("\p-00123",
                  &x);
    cout << x << endl;

    ::StringToNum("\p  123",
                  &x);
    cout << x << endl;
    ::StringToNum("\p+  123",
                  &x);
    cout << x << endl;
    ::StringToNum("\p-  123",
                  &x);
    cout << x << endl;

    ::StringToNum("\p  00123",
                  &x);
    cout << x << endl;
    ::StringToNum("\p+  00123",
                  &x);
    cout << x << endl;
    ::StringToNum("\p-  00123",
                  &x);
    cout << x << endl;

    ::StringToNum("\p  -123",
                  &x);
    cout << x << endl; // -> 13123.
    ::StringToNum("\p  -00123",
                  &x);
    cout << x << endl; // -> 1300123.

    return 0;
}

[OS923]

I have a solution that is 2.5% faster than Apple.

[GaryN]

There are 10 kinds of people in the world

Those who understand binary and those who don't

[OS923]

There are 2 kinds of people: those who start counting from 1, and those who start counting from 0.