Hi,
given a list of digits '(1 2 3), I want to get the number 123
represented by the digits. I want this to work with any base and any
number of digits. Execution speed is rather important.
The obvious way to do this would perhaps be (in the case of base 10) to
just do (+ (* 100 1) (* 10 2) (* 1 3)), but perhaps there is a
better/more elegant way?
--
Frode, SIM
"Any fool can write code that a computer can understand.
Good programmers write code that humans can understand"
Frode �ijord wrote:
> Hi,
> given a list of digits '(1 2 3), I want to get the number 123
> represented by the digits. I want this to work with any base and any
> number of digits. Execution speed is rather important.
>
> The obvious way to do this would perhaps be (in the case of base 10) to
> just do (+ (* 100 1) (* 10 2) (* 1 3)), but perhaps there is a
> better/more elegant way?
There are basically two ways, either
123 = 3*1 + 2*10 + 1*100
or
123 = (1*10 + 2)*10 + 3 .
I think you have to try both to see which is fastest.
--
Jens Axel S�gaard
On Mon, 10 Apr 2006 12:02:28 +0200, <······@soegaard.net> wrote:
>
> There are basically two ways, either
>
> 123 = 3*1 + 2*10 + 1*100
>
> or
>
> 123 = (1*10 + 2)*10 + 3 .
>
> I think you have to try both to see which is fastest.
Since the second method is an old hand calculator trick, and by
inspection contains one less multiply, it is clearly faster. But I
didn't see any need to multiply in the OP.
--
If you use SLIME, it will categorize compiler noise for you into
Errors, Warnings, and Notes. Lets see VI match that!
*** Free account sponsored by SecureIX.com ***
*** Encrypt your Internet usage with a free VPN account from http://www.SecureIX.com ***
In article <·························@dread12.news.tele.dk>,
=?ISO-8859-1?Q?Jens_Axel_S=F8gaard?= <······@soegaard.net> wrote:
>Frode �ijord wrote:
>> Hi,
>> given a list of digits '(1 2 3), I want to get the number 123
>> represented by the digits. I want this to work with any base and any
>> number of digits. Execution speed is rather important.
>>
>> The obvious way to do this would perhaps be (in the case of base 10) to
>> just do (+ (* 100 1) (* 10 2) (* 1 3)), but perhaps there is a
>> better/more elegant way?
>
>There are basically two ways, either
>
> 123 = 3*1 + 2*10 + 1*100
>
>or
>
> 123 = (1*10 + 2)*10 + 3 .
>
>I think you have to try both to see which is fastest.
If the lists are long (tens of thousands of digits) and you have
efficient multiplication and exponentiation, it's asymptotically much
more efficient to split the list in two, and compute
(+ (decimalise right)
(* (expt base (length right)) (decimalise left)))
then recurse. It's also worth doing much the same thing in reverse
for printing large bignums and for the 'write the digits in this
number backwards' useless primitive.
Tom
Thomas Womack wrote:
> It's also worth doing much the same thing in reverse
> for printing large bignums and for the 'write the digits in this
> number backwards' useless primitive.
I would trust in fast native implementations of Common Lisp functions:
(defun backward (number)
(parse-integer (reverse (write-to-string number))))
--
Frank Buss, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
Frank Buss wrote:
> (defun backward (number)
> (parse-integer (reverse (write-to-string number))))
and in the spirit of Pascal's solutions:
(defun backward (number &optional (base 10))
(reduce-number (split-backward number base) base))
(defun reduce-number (digits &optional (base 10))
(reduce (lambda (n digit) (+ (* n base) digit)) digits))
(defun split-backward (number &optional (base 10))
(loop while (< 0 number) collect
(multiple-value-bind (quotient remainder) (floor number base)
(setf number quotient)
remainder)))
LOOP is ok, but I wonder if there is a more elegant contruct like REDUCE
for the opposite concept for building a list. Building the list should not
need more program code characters than reducing the list.
--
Frank Buss, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
Frode �ijord wrote:
> The obvious way to do this would perhaps be (in the case of base 10) to
> just do (+ (* 100 1) (* 10 2) (* 1 3)), but perhaps there is a
> better/more elegant way?
yes:
(parse-integer (coerce (mapcar #'digit-char '(1 2 3)) 'string))
parse-integer has an optional argument for the base.
--
Frank Buss, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
Frank Buss wrote:
> Frode �ijord wrote:
>
>
>>The obvious way to do this would perhaps be (in the case of base 10) to
>>just do (+ (* 100 1) (* 10 2) (* 1 3)), but perhaps there is a
>>better/more elegant way?
>
>
> yes:
>
> (parse-integer (coerce (mapcar #'digit-char '(1 2 3)) 'string))
>
> parse-integer has an optional argument for the base.
>
Sweet... This is pretty much what I was looking for.
--
Frode, SIM
"Any fool can write code that a computer can understand.
Good programmers write code that humans can understand"
Frode �ijord <·····@sim.no> writes:
> Frank Buss wrote:
>> Frode �ijord wrote:
>>
>>> The obvious way to do this would perhaps be (in the case of base
>>> 10) to just do (+ (* 100 1) (* 10 2) (* 1 3)), but perhaps there is
>>> a better/more elegant way?
>> yes:
>> (parse-integer (coerce (mapcar #'digit-char '(1 2 3)) 'string))
>> parse-integer has an optional argument for the base.
>>
> Sweet... This is pretty much what I was looking for.
Is it really? You asked for any base!
How about converting 31.24.51.11.2 from base 55?
(let ((digits (list 31 24 51 11 2))
(base 55))
(reduce (lambda (n digit) (+ (* n base) digit)) digits
:initial-value 0))
--> 287817257
Or 24.0.0 from base 60?
(let ((digits (list 24 0 0))
(base 60))
(reduce (lambda (n digit) (+ (* n base) digit)) digits
:initial-value 0))
--> 86400
--
__Pascal Bourguignon__ http://www.informatimago.com/
PLEASE NOTE: Some quantum physics theories suggest that when the
consumer is not directly observing this product, it may cease to
exist or will exist only in a vague and undetermined state.
Pascal Bourguignon wrote:
> Frode �ijord <·····@sim.no> writes:
>
>
>>Frank Buss wrote:
>>
>>>Frode �ijord wrote:
>>>
>>>
>>>>The obvious way to do this would perhaps be (in the case of base
>>>>10) to just do (+ (* 100 1) (* 10 2) (* 1 3)), but perhaps there is
>>>>a better/more elegant way?
>>>
>>>yes:
>>>(parse-integer (coerce (mapcar #'digit-char '(1 2 3)) 'string))
>>>parse-integer has an optional argument for the base.
>>>
>>
>>Sweet... This is pretty much what I was looking for.
>
>
> Is it really? You asked for any base!
>
> How about converting 31.24.51.11.2 from base 55?
>
> (let ((digits (list 31 24 51 11 2))
> (base 55))
> (reduce (lambda (n digit) (+ (* n base) digit)) digits
> :initial-value 0))
> --> 287817257
>
>
> Or 24.0.0 from base 60?
>
> (let ((digits (list 24 0 0))
> (base 60))
> (reduce (lambda (n digit) (+ (* n base) digit)) digits
> :initial-value 0))
> --> 86400
>
I see your point... parse-integer only supports bases from 2 to 36. I
don't really need bases bigger than 13 for now, but I guess its a bit
silly to create a string and then parse it to get a number from a list
of digits.
--
Frode, SIM
"Any fool can write code that a computer can understand.
Good programmers write code that humans can understand"
> I see your point... parse-integer only supports bases from 2 to 36. I
> don't really need bases bigger than 13 for now, but I guess its a bit
> silly to create a string and then parse it to get a number from a list
> of digits.
Note that the coercion approach needs a slight modification to work
with bases greater than 10, because 10 is the default radix. You'd
need to set the radix, too:
(defun join-digit-list (list &optional (base 10))
(parse-integer (coerce (mapcar (lambda (d) (digit-char d base))
list) 'string) :radix base))
Frode �ijord <·····@sim.no> writes:
> I see your point... parse-integer only supports bases from 2 to 36. I don't
> really need bases bigger than 13 for now, but I guess its a bit silly to
> create a string and then parse it to get a number from a list of digits.
I wouldn't worry too much about it unless you've got some reason to. From a
computational point of view this code might be braindead, but cognitively it
is presumably as good as you'll get [1]. Why trade off expensive brain-cycles for
cheap computer cycles unless there's a real need?
'as
[1] Apart possibly from the emotional overhead the blatant inefficiency of the
solution could cause some people.
Pascal Bourguignon wrote:
> (let ((digits (list 31 24 51 11 2))
> (base 55))
> (reduce (lambda (n digit) (+ (* n base) digit)) digits
> :initial-value 0))
That's better. But you don't need the ":initial-value", unless you want to
call it with an empty list.
--
Frank Buss, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de