# Fastest way to loop through each digit in a number?

Discussion in 'Python' started by Rune Strand, Sep 6, 2004.

1. ### Rune StrandGuest

Hi,
If I have a lot of integers and want do something with each digit as
integer, what is the fastest way to get there?

Eg. Make 12345 into an iterable object, like [1,2,3,4,5] or "12345"

(Btw: What is the English term for this process; itemize? tokenize?
digitize? sequence?)

Some examples:

n = 12345

#1.
s = str(n)
for i in s:
d = int(i)
foo(d)

#2.
nl = map(int, str(n))
for d in nl:
foo(d)

#3.
nl = [int(x) for x in str(n)]
for d in nl:
foo(d)

Of those, I have, a bit surprised, found that #1 is the fastest, and
that #2 using map() is faster than #3 using list comprehension. I also
registered that that repr(n) is about 8% faster than str(n).

Are there faster ways? Is it possible to avoid casting types?

Rune Strand, Sep 6, 2004

2. ### Roy SmithGuest

In article <>,
Rune Strand <rst@_nospam_.drlug.org._nospam_> wrote:

> Hi,
> If I have a lot of integers and want do something with each digit as
> integer, what is the fastest way to get there?
>
> Eg. Make 12345 into an iterable object, like [1,2,3,4,5] or "12345"

Does it matter what order you process the digits, i.e. least-significant
first vs. most-significant first? If you can do least first, then you
might be best off doing something straight-forward like:

i = 12345
while i:
digit = i % 10
i = i / 10
print digit

although, with the new-style division, I'm not sure if you want / or //.

Roy Smith, Sep 6, 2004

3. ### Paul RubinGuest

Rune Strand <rst@_nospam_.drlug.org._nospam_> writes:
You could try timing something like

while n:
n,d = divmod(n, 10)
foo(d)

That processes the digits in reverse order, of course.

Paul Rubin, Sep 6, 2004
4. ### Rune StrandGuest

Paul Rubin <http://> wrote:

>You could try timing something like
>
> while n:
> n,d = divmod(n, 10)
> foo(d)
>
>That processes the digits in reverse order, of course.

Thanks!
It's faster! But Roy Smiths modulus (%) method is even faster. The
order does matter, but even when appending d to a list inside the loop
and reversing it when done, your methods are faster than my initial
groks ;-)

Rune Strand, Sep 6, 2004
5. ### Terry ReedyGuest

"Rune Strand" <rst@_nospam_.drlug.org._nospam_> wrote in message
news:...
> Hi,
> If I have a lot of integers and want do something with each digit as
> integer, what is the fastest way to get there?
>
> Eg. Make 12345 into an iterable object, like [1,2,3,4,5] or "12345"
>
> (Btw: What is the English term for this process; itemize? tokenize?
> digitize? sequence?)
>
> Some examples:

You might also look at

zero = ord('0')

and then ord(i)-zero in loop

tjr

Terry Reedy, Sep 6, 2004

n2 = n
while n2 > 0:
d = n2 % 10
n2 /= 10
foo(d)

7. ### Alex MartelliGuest

Roy Smith <> wrote:

> In article <>,
> Rune Strand <rst@_nospam_.drlug.org._nospam_> wrote:
>
> > Hi,
> > If I have a lot of integers and want do something with each digit as
> > integer, what is the fastest way to get there?
> >
> > Eg. Make 12345 into an iterable object, like [1,2,3,4,5] or "12345"

>
> Does it matter what order you process the digits, i.e. least-significant
> first vs. most-significant first? If you can do least first, then you
> might be best off doing something straight-forward like:
>
> i = 12345
> while i:
> digit = i % 10
> i = i / 10
> print digit
>
> although, with the new-style division, I'm not sure if you want / or //.

He'd surely want truncation, so I don't understand why he could possibly
want / (which in new-style division means true, non-truncating
division), it's surely gotta be //. divmod looks like it might be
better, but from some q&d timeit.py'ing, it seems this approach is
fastest (30% faster than divmod) if these semantics are OK (when i is 0
you get nothing rather than a single 0...) -- map(int, str(i)) is midway
in speed through these purely numeric approaches (with % and // vs with
divmod).

Alex

Alex Martelli, Sep 6, 2004
8. ### Rune StrandGuest

On Mon, 6 Sep 2004 02:32:46 -0400, "Terry Reedy" <>
wrote:

> You might also look at
>
>zero = ord('0')
>
>and then ord(i)-zero in loop

Thanks! That seems like the fastest solution.
When looping through 1000000, I get these results:
ord : 4.703 (Terry Reedy)
divmod : 10.469 (Paul Rubin)
modulo : 7.625 (Roy Smith)
lst comp: 11.750
map : 9.062
str : 8.219

The modulo and divmod methods includes list.append(d) and
list.reverse() (list.append mapped to list_append).

Rune Strand, Sep 6, 2004
9. ### Rune StrandGuest

;-) Somtimes the solition is too obvious... faster than using ord()
is to look up the value in a map:

dictmap = {
'0' : 0,
'1' : 1,
'2' : 2,
'3' : 3,
'4' : 4,
'5' : 5,
'6' : 6,
'7' : 7,
'8' : 8,
'9' : 9
}

def each_dig_in_num(n):
dm = dictmap #faster if local
s = repr(n) #repr is faster than str
for char in s:
foo(dm[char])

Rune Strand, Sep 6, 2004
10. ### Bengt RichterGuest

On Mon, 06 Sep 2004 04:56:54 +0200, Rune Strand <rst@_nospam_.drlug.org._nospam_> wrote:

>Hi,
>If I have a lot of integers and want do something with each digit as
>integer, what is the fastest way to get there?
>

How many is "a lot" ? And what are the bounds on your integers' values? ;-)
Keep in mind that whatever you are computing, it is a mapping from imput to output,
and sometimes it pays to implement a subproblem literally as a mapping.

>Eg. Make 12345 into an iterable object, like [1,2,3,4,5] or "12345"

E.g., if you had a bazillion numbers that were all positive and five digits max,
then your fastest mapping from number to digit sequence would probably be a precomputed
list or tuple with data like (untested):

digitseqs = [[0],[1],[2],...[8],[9],[1,0],[1,1],[1,2]... [1,2,3,4,5],[1,2,3,4,6], ... [9,9,9,9,9]]

and then there would be no computation of the digits in

for d in digitseqs[number]:
foo(d)

If your numbers are bigger, you can still use the same technique, chunkwise, e.g.,
if you know you have positive 32-bit integers, that's 0<= number <= 1073741824

if number >= 1000000000:
foo(1)
number -= 1000000000
low5 = number % 100000
for d in digitseqs[number//100000]: foo(d)
for d in zdigitseqs[low5]: foo(d)

(zdigitseqs are all 5-digit sequences with leading zeroes included, [[0,0,0,0,0],[0,0,0,0,1], ...])

If your numbers are unbounded, you can still do something along these lines, but
numbers have to be _huge_ before you gain more than you lose in complication.
You could wrap the above in a function like def fooit(number, foo=foofunc): ...
but calls are relatively expensive in time, so you may want to forego the nicer style.

Obviously 100k lists of lists take a fair chunk of memory, and take a little time to
pre-compute, but it may pay off if you have REALLY "a lot" of input numbers ;-)

>
>(Btw: What is the English term for this process; itemize? tokenize?
>digitize? sequence?)
>
>Some examples:
>
>n = 12345
>
>#1.
>s = str(n)
>for i in s:
> d = int(i)
> foo(d)
>
>#2.
>nl = map(int, str(n))
>for d in nl:
> foo(d)
>
>#3.
>nl = [int(x) for x in str(n)]
>for d in nl:
> foo(d)
>
>Of those, I have, a bit surprised, found that #1 is the fastest, and
>that #2 using map() is faster than #3 using list comprehension. I also
>registered that that repr(n) is about 8% faster than str(n).
>
>Are there faster ways? Is it possible to avoid casting types?
>
>

I haven't timed the above (or even tested it), but your gains (if any ;-) will depend on