Re: Fast Binary-to-Decimal Conversion Algorithms?

From: Richard Harter (cri_at_tiac.net)
Date: 08/03/04 

Date: Tue, 03 Aug 2004 08:02:40 GMT

On Mon, 02 Aug 2004 20:57:39 GMT, CBFalconer <cbfalconer@yahoo.com>
wrote:

>Richard Harter wrote:
>> CBFalconer <cbfalconer@yahoo.com> wrote:
>>> Simon G Best wrote:
>>>>
>>>> Without much success, I've been trying to find a 'fast' algorithm
>>>> for converting large numbers from binary to decimal. By 'fast',
>>>> I mean something like O(N log(N)). By 'large', I mean billions
>>>> of bits. Oh, and I'd like a similarly fast algorithm for
>>>> converting back from decimal to binary, too, please. Oh, and
>>>> yes, I'd like fries with that :-)
>>>
>>> Back in April I posted something here and on comp.arch.embedded.
>>> The subject included the words "double" and "dabble". At any
>>> rate, you can find it at:
>>>
>>> <http://cbfalconer.home.att.net/download/dubldabl.txt>
>>
>> Dabble is a good O(n^2) algorithm; on the scale that he is talking
>> about he needs the kind of stuff that they use in gmp.
>
>On the contrary, the last modification I showed in that article
>was of an algorithm of O(N). You may wish to read it. The
>process is reversible, so it supplies all the fries Simon Best
>wanted. Here is an extract of the table for that last:
>
>--------------- extract ---------
>Now alter the ADD-3 rule to say - Add 3 whenever the digit value
>is 5 or more, AND the digit is entirely to the right of the x
>marker, inclusive. Notice that the ADD-3 to TENS suddenly is
>back in effect. So are two new dabbles, marked by <-- below.
>
> ----BINARY----
>INDEX THOU HUND TENS UNITS
> 0 11 1111 1111 x000 Start
> 1 11 1111 111x 0001 Shift 1
> 2 11 1111 11x0 0011 Shift 2
> 3 11 1111 1x00 0111 Shift 3
> 4 11 1111 1x00 1010 ADD-3 to UNITS
> 4 11 1111 x001 0101 Shift 4
> 5 11 1111 x001 1000 ADD-3 to UNITS
> 5 11 111x 0011 0001 Shift 5
> 6 11 11x0 0110 0011 Shift 6
> 7 11 11x0 1001 0011 ADD-3 to TENS (live)
> 7 11 1x01 0010 0111 Shift 7
> 8 11 1x01 0010 1010 ADD-3 to UNITS
> 8 11 x010 0101 0101 Shift 8
> 9 11 x010 0101 1000 ADD-3 to UNITS
> 9 11 x010 1000 1000 ADD-3 to TENS <--
> 9 1x 0101 0001 0001 Shift 9
> 10 1x 1000 0001 0001 ADD-3 to HUND <--
> 10 x1 0000 0010 0011 Shift 10
> | <-- ^
> v_________________|
>--------- end extract -----------
>
>and you will notice that conversion of a 10 bit number requires 10
>operations. I will concede in advance that this requires an O(1)
>shift operation, i.e. a register long enough to hold the value.
>In hardware this is easy, and all I need to do is cascade a mess
>of 4 bit modules. In software, with fixed size registers, it is
>probably another matter. That is an implementation detail :-)

Er, yes, an implementation detail. Good show. Unfortunately the
fusspots are going to count moving n bits as an O(n) operation.
It's a nice algorithm and you have a good writeup, but it's still
an O(n^2) algorithm.

Richard Harter, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Whoever said money can't buy happiness
didn't know where to shop.

Relevant Pages

  • Re: data mining algorithm plug-in problem
    ... Something is wrong with ProgID. ... > You do not need to copy the PlugInAlgorithm, once you register it, and I ... > You need to restart Analysis Services once you change the INI file. ... > message that your algorithm was loaded successfully, ...
    (microsoft.public.sqlserver.datamining)
  • Re: data mining algorithm plug-in problem
    ... SQL Server Data Mining ... >> You do not need to copy the PlugInAlgorithm, once you register it, and I ... >> You need to restart Analysis Services once you change the INI file. ... >> message that your algorithm was loaded successfully, ...
    (microsoft.public.sqlserver.datamining)
  • Re: Fast Binary-to-Decimal Conversion Algorithms?
    ... > Dabble is a good Oalgorithm; on the scale that he is talking ... was of an algorithm of O. ... shift operation, i.e. a register long enough to hold the value. ...
    (comp.programming)
  • MD5 Weakness Exploited
    ... While reading 'The Register' this evening, ... shared with the SHA-1 algorithm. ... MD5 check sums to prove that their program, data file, etc. has not ... computing hash values (check sums) and consider MD5 sums as worthless. ...
    (comp.os.os2.apps)
  • Re: Public domain algorithm for arbitrary-precision fast division?
    ... David N. Williams wrote: ... >> I'm looking for an algorithm for doing arbitrary-precision ... the fastest method uses fast multiplication by two steps. ... I've never used it, but I must say that from the outside, GMP ...
    (sci.math.num-analysis)
Loading