Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]


Groups > comp.soft-sys.math.mathematica > #5348 > unrolled thread

Re: count zeros in a number

Started by"Harvey P. Dale" <hpd1@nyu.edu>
First post2011-10-03 08:32 +0000
Last post2011-10-05 08:13 +0000
Articles 8 — 4 participants

Back to article view | Back to comp.soft-sys.math.mathematica

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.


Contents

  Re: count zeros in a number "Harvey P. Dale" <hpd1@nyu.edu> - 2011-10-03 08:32 +0000
    Re: count zeros in a number Richard Fateman <fateman@cs.berkeley.edu> - 2011-10-04 05:31 +0000
    Re: count zeros in a number DrMajorBob <btreat1@austin.rr.com> - 2011-10-05 08:05 +0000
    Re: count zeros in a number Richard Fateman <fateman@eecs.berkeley.edu> - 2011-10-05 08:08 +0000
    Re: count zeros in a number DrMajorBob <btreat1@austin.rr.com> - 2011-10-05 08:09 +0000
    Re: count zeros in a number DrMajorBob <btreat1@austin.rr.com> - 2011-10-05 08:11 +0000
    Re: count zeros in a number Richard Fateman <fateman@eecs.berkeley.edu> - 2011-10-05 08:12 +0000
    Re: count zeros in a number DrMajorBob <btreat1@austin.rr.com> - 2011-10-05 08:13 +0000

#5348 — Re: count zeros in a number

From"Harvey P. Dale" <hpd1@nyu.edu>
Date2011-10-03 08:32 +0000
SubjectRe: count zeros in a number
Message-ID<j6brvm$8om$1@smc.vnet.net>
=09
zeroes[n_]:=Module[{idn=IntegerDigits[n]},If[Last[idn]==0,Length[Split[i
dn][[-1]]],0]]
	zeroes[24^24 55^55]

	Best,

	Harvey

-----Original Message-----
From: dimitris [mailto:dimmechan@yahoo.com]
Sent: Sunday, October 02, 2011 2:37 AM
Subject: count zeros in a number

Hello.

Consider e.g. the number 24^24*55^55.
This number ends with exactly 55 zeros as the following demonstrate

In[201]:= Mod[24^24*55^55, 10^55]
Mod[24^24*55^55, 10^56]

Out[201]= 0
Out[202]= 20000000000000000000000000000000000000000000000000000000


What I want now is a way to count the zeros that a number ends without
knowing in advance this number of zeros like in the above example.

Thanks in advance.
Dimitris

[toc] | [next] | [standalone]


#5361

FromRichard Fateman <fateman@cs.berkeley.edu>
Date2011-10-04 05:31 +0000
Message-ID<j6e5nq$k8m$1@smc.vnet.net>
In reply to#5348
How disappointing that the usual crew did not come up with a way of 
solving this simply, arithmetically, like this:

(n = 0; While[GCD[24^24*55^55, 10^n] == 10^n, n++]; n - 1)

or

(n = 0; x = 24^24*55^55;
  While[Mod[x, 10] == 0, (x = x/10; n++)  ]; n)

or any of the numerous minor variants....

but instead resorted to conversion to strings or factoring.

The arithmentic methods may be slower since they rely on the slow 
implementation of looping constructs in Mathematica, but they
don't require any of the more esoteric features like
Exponents, Split, IntegerDigits, ...

RJF

[toc] | [prev] | [next] | [standalone]


#5382

FromDrMajorBob <btreat1@austin.rr.com>
Date2011-10-05 08:05 +0000
Message-ID<j6h34e$70f$1@smc.vnet.net>
In reply to#5348
There's nothing "esoteric" about IntegerDigits, Replace, or Repeated, as  
in:

x = 24^24*55^55;
Replace[IntegerDigits@x, {__, zeroes : 0 ..} :>
    Length@{zeroes}] // Timing

{0.000185, 55}

If we wanted brute-force arithmetic, we might use Fortran.

Your suggested solutions are NOT greatly hindered by "the slow  
implementation of looping constructs in Mathematica", on the other hand:

(n = 0; While[GCD[x, 10^n] == 10^n, n++]; n - 1) // Timing

{0.000029, 0}

(n = 0; While[Mod[x, 10] == 0, (x = x/10; n++)]; n) // Timing

{0.000018, 0}

Bobby

On Tue, 04 Oct 2011 00:30:21 -0500, Richard Fateman  
<fateman@cs.berkeley.edu> wrote:

> How disappointing that the usual crew did not come up with a way of
> solving this simply, arithmetically, like this:
>
> (n = 0; While[GCD[24^24*55^55, 10^n] == 10^n, n++]; n - 1)
>
> or
>
> (n = 0; x = 24^24*55^55;
>   While[Mod[x, 10] == 0, (x = x/10; n++)  ]; n)
>
> or any of the numerous minor variants....
>
> but instead resorted to conversion to strings or factoring.
>
> The arithmentic methods may be slower since they rely on the slow
> implementation of looping constructs in Mathematica, but they
> don't require any of the more esoteric features like
> Exponents, Split, IntegerDigits, ...
>
> RJF
>


-- 
DrMajorBob@yahoo.com

[toc] | [prev] | [next] | [standalone]


#5392

FromRichard Fateman <fateman@eecs.berkeley.edu>
Date2011-10-05 08:08 +0000
Message-ID<j6h397$721$1@smc.vnet.net>
In reply to#5348
On 10/4/2011 9:44 AM, DrMajorBob wrote:
> There's nothing "esoteric" about IntegerDigits, Replace, or Repeated, 
> as in:
>
> x = 24^24*55^55;
> Replace[IntegerDigits@x, {__, zeroes : 0 ..} :>
>    Length@{zeroes}] // Timing
>
> {0.000185, 55}

My feeling is that these ARE esoteric.  A person just introduced to 
Mathematica would probably not encounter IntegerDigits, Repeated, or 
patterns other than the trivial one used in pseudo function definitions as
f[x_]:=   x+1.


>
> If we wanted brute-force arithmetic, we might use Fortran.
>
> Your suggested solutions are NOT greatly hindered by "the slow 
> implementation of looping constructs in Mathematica", on the other hand:
>
> (n = 0; While[GCD[x, 10^n] == 10^n, n++]; n - 1) // Timing
>
> {0.000029, 0}

huh?   I got  {0., 55}.   Perhaps my computer is faster or has a lower 
resolution timer, but we should both get 55.

>
> (n = 0; While[Mod[x, 10] == 0, (x = x/10; n++)]; n) // Timing
>
> {0.000018, 0}

I mention the slow implementation of looping constructs simply to warn 
people that if you can resolve your computation by simple composition of 
built-in functions e.g. F[G[H[x]]]   and don't rely on Mathematica
to efficiently execute loops written as While[] For[]  etc, you are 
probably going to run faster.  Let Mathematica's operation on compound 
objects like lists do the job.  Length[] is a lot faster than counting 
with a While etc.

In my timings, doing the operations 1000 times..
Do[.....,{1000}]//Timing

I found that my solutions were about 10X faster than the IntegerDigits 
one, on this particular value of x.

Fortran can't be used unless you manage arbitrary precision integers...

RJF



[toc] | [prev] | [next] | [standalone]


#5395

FromDrMajorBob <btreat1@austin.rr.com>
Date2011-10-05 08:09 +0000
Message-ID<j6h3c3$72s$1@smc.vnet.net>
In reply to#5348
A person just introduced to Mathematica is NOT, as yet, a Mathematica  
programmer.

Bobby

On Tue, 04 Oct 2011 15:57:30 -0500, Richard Fateman  
<fateman@eecs.berkeley.edu> wrote:

> On 10/4/2011 9:44 AM, DrMajorBob wrote:
>> There's nothing "esoteric" about IntegerDigits, Replace, or Repeated,  
>> as in:
>>
>> x = 24^24*55^55;
>> Replace[IntegerDigits@x, {__, zeroes : 0 ..} :>
>>    Length@{zeroes}] // Timing
>>
>> {0.000185, 55}
>
> My feeling is that these ARE esoteric.  A person just introduced to  
> Mathematica would probably not encounter IntegerDigits, Repeated, or  
> patterns other than the trivial one used in pseudo function definitions  
> as
> f[x_]:=   x+1.
>
>
>>
>> If we wanted brute-force arithmetic, we might use Fortran.
>>
>> Your suggested solutions are NOT greatly hindered by "the slow  
>> implementation of looping constructs in Mathematica", on the other hand:
>>
>> (n = 0; While[GCD[x, 10^n] == 10^n, n++]; n - 1) // Timing
>>
>> {0.000029, 0}
>
> huh?   I got  {0., 55}.   Perhaps my computer is faster or has a lower  
> resolution timer, but we should both get 55.
>
>>
>> (n = 0; While[Mod[x, 10] == 0, (x = x/10; n++)]; n) // Timing
>>
>> {0.000018, 0}
>
> I mention the slow implementation of looping constructs simply to warn  
> people that if you can resolve your computation by simple composition of  
> built-in functions e.g. F[G[H[x]]]   and don't rely on Mathematica
> to efficiently execute loops written as While[] For[]  etc, you are  
> probably going to run faster.  Let Mathematica's operation on compound  
> objects like lists do the job.  Length[] is a lot faster than counting  
> with a While etc.
>
> In my timings, doing the operations 1000 times..
> Do[.....,{1000}]//Timing
>
> I found that my solutions were about 10X faster than the IntegerDigits  
> one, on this particular value of x.
>
> Fortran can't be used unless you manage arbitrary precision integers...
>
> RJF
>
>
>


-- 
DrMajorBob@yahoo.com

[toc] | [prev] | [next] | [standalone]


#5398

FromDrMajorBob <btreat1@austin.rr.com>
Date2011-10-05 08:11 +0000
Message-ID<j6h3ev$73m$1@smc.vnet.net>
In reply to#5348
I'm guessing that I got zero because I ran some of the code with an  
undefined x. My bad!

Correcting that, I find the esoteric method faster than your ancient,  
outmoded ones:

x = 24^24*55^55;
Replace[IntegerDigits@x, {__, zeroes : 0 ..} :>
    Length@{zeroes}] // Timing

{0.000198, 55}

(n = 0; While[GCD[x, 10^n] == 10^n, n++]; n - 1) // Timing

{0.000417, 55}

(n = 0; While[Mod[x, 10] == 0, (x = x/10; n++)]; n) // Timing

{0.000228, 55}

Bobby

On Tue, 04 Oct 2011 15:57:30 -0500, Richard Fateman  
<fateman@eecs.berkeley.edu> wrote:

> On 10/4/2011 9:44 AM, DrMajorBob wrote:
>> There's nothing "esoteric" about IntegerDigits, Replace, or Repeated,  
>> as in:
>>
>> x = 24^24*55^55;
>> Replace[IntegerDigits@x, {__, zeroes : 0 ..} :>
>>    Length@{zeroes}] // Timing
>>
>> {0.000185, 55}
>
> My feeling is that these ARE esoteric.  A person just introduced to  
> Mathematica would probably not encounter IntegerDigits, Repeated, or  
> patterns other than the trivial one used in pseudo function definitions  
> as
> f[x_]:=   x+1.
>
>
>>
>> If we wanted brute-force arithmetic, we might use Fortran.
>>
>> Your suggested solutions are NOT greatly hindered by "the slow  
>> implementation of looping constructs in Mathematica", on the other hand:
>>
>> (n = 0; While[GCD[x, 10^n] == 10^n, n++]; n - 1) // Timing
>>
>> {0.000029, 0}
>
> huh?   I got  {0., 55}.   Perhaps my computer is faster or has a lower  
> resolution timer, but we should both get 55.
>
>>
>> (n = 0; While[Mod[x, 10] == 0, (x = x/10; n++)]; n) // Timing
>>
>> {0.000018, 0}
>
> I mention the slow implementation of looping constructs simply to warn  
> people that if you can resolve your computation by simple composition of  
> built-in functions e.g. F[G[H[x]]]   and don't rely on Mathematica
> to efficiently execute loops written as While[] For[]  etc, you are  
> probably going to run faster.  Let Mathematica's operation on compound  
> objects like lists do the job.  Length[] is a lot faster than counting  
> with a While etc.
>
> In my timings, doing the operations 1000 times..
> Do[.....,{1000}]//Timing
>
> I found that my solutions were about 10X faster than the IntegerDigits  
> one, on this particular value of x.
>
> Fortran can't be used unless you manage arbitrary precision integers...
>
> RJF
>
>
>


-- 
DrMajorBob@yahoo.com

[toc] | [prev] | [next] | [standalone]


#5401

FromRichard Fateman <fateman@eecs.berkeley.edu>
Date2011-10-05 08:12 +0000
Message-ID<j6h3hr$74b$1@smc.vnet.net>
In reply to#5348
On 10/4/2011 2:33 PM, DrMajorBob wrote:
> I'm guessing that I got zero because I ran some of the code with an 
> undefined x. My bad!


I think that you (me too)  might not have noticed that one of my methods 
changed x.  Here is a safer version.

savedx= 24^24*55^55;


Well, here's another method..

(xs = ToString[savedx];
  StringLength[xs] -   
StringLength[ToString[ToExpression[StringReverse[xs]]]])

Let's time it, running 1000 times.

Do[ (xs = ToString[savedx];
    StringLength[xs] -
     StringLength[
      ToString[ToExpression[StringReverse[xs]]]]), {1000}] // Timing

{0.063,Null}

This bizarre hack  is reasonably fast, indeed twice as fast  as your 
method, on my system.

Do[Replace[
    IntegerDigits@x, {__, zeroes : 0 ..} :>
     Length@{zeroes}], {1000}] // Timing

{0.141, Null}

and seven times as fast as my older simple arithmetic method which uses 
iteration,


Do[(n = 0; x = savedx; While[Mod[x, 10] == 0, (x = x/10; n++)];
    n), {1000}] // Timing

{0.438, Null}

and which (as I contended) was inefficient in Mathematica.  While you 
seem to think that this method is ancient and outmoded, I think it is 
not the method, but the implementation of iteration. Or perhaps of 
arithmetic?

Another implementation of this arithmetical method on the same computer 
takes 0.063 seconds.

RJF

>
> Correcting that, I find the esoteric method faster than your ancient, 
> outmoded ones:
>
> x = 24^24*55^55;
> Replace[IntegerDigits@x, {__, zeroes : 0 ..} :>
>    Length@{zeroes}] // Timing
>
> {0.000198, 55}
>
> (n = 0; While[GCD[x, 10^n] == 10^n, n++]; n - 1) // Timing
>
> {0.000417, 55}
>
> (n = 0; While[Mod[x, 10] == 0, (x = x/10; n++)]; n) // Timing
>
> {0.000228, 55}
>
> Bobby
>
> On Tue, 04 Oct 2011 15:57:30 -0500, Richard Fateman 
> <fateman@eecs.berkeley.edu> wrote:
>
>> On 10/4/2011 9:44 AM, DrMajorBob wrote:
>>> There's nothing "esoteric" about IntegerDigits, Replace, or 
>>> Repeated, as in:
>>>
>>> x = 24^24*55^55;
>>> Replace[IntegerDigits@x, {__, zeroes : 0 ..} :>
>>>    Length@{zeroes}] // Timing
>>>
>>> {0.000185, 55}
>>
>> My feeling is that these ARE esoteric.  A person just introduced to 
>> Mathematica would probably not encounter IntegerDigits, Repeated, or 
>> patterns other than the trivial one used in pseudo function 
>> definitions as
>> f[x_]:=   x+1.
>>
>>
>>>
>>> If we wanted brute-force arithmetic, we might use Fortran.
>>>
>>> Your suggested solutions are NOT greatly hindered by "the slow 
>>> implementation of looping constructs in Mathematica", on the other 
>>> hand:
>>>
>>> (n = 0; While[GCD[x, 10^n] == 10^n, n++]; n - 1) // Timing
>>>
>>> {0.000029, 0}
>>
>> huh?   I got  {0., 55}.   Perhaps my computer is faster or has a 
>> lower resolution timer, but we should both get 55.
>>
>>>
>>> (n = 0; While[Mod[x, 10] == 0, (x = x/10; n++)]; n) // Timing
>>>
>>> {0.000018, 0}
>>
>> I mention the slow implementation of looping constructs simply to 
>> warn people that if you can resolve your computation by simple 
>> composition of built-in functions e.g. F[G[H[x]]]   and don't rely on 
>> Mathematica
>> to efficiently execute loops written as While[] For[]  etc, you are 
>> probably going to run faster.  Let Mathematica's operation on 
>> compound objects like lists do the job.  Length[] is a lot faster 
>> than counting with a While etc.
>>
>> In my timings, doing the operations 1000 times..
>> Do[.....,{1000}]//Timing
>>
>> I found that my solutions were about 10X faster than the 
>> IntegerDigits one, on this particular value of x.
>>
>> Fortran can't be used unless you manage arbitrary precision integers...
>>
>> RJF
>>
>>
>>
>
>

[toc] | [prev] | [next] | [standalone]


#5402

FromDrMajorBob <btreat1@austin.rr.com>
Date2011-10-05 08:13 +0000
Message-ID<j6h3iq$74k$1@smc.vnet.net>
In reply to#5348
This does the same thing as your code, essentially:

x = 24^24*55^55;
xd = IntegerDigits@x;
Length@xd - Length@IntegerDigits@FromDigits@Reverse@xd

55

and there's no reason for ToString to be faster than IntegerDigits, so...

Do[xd = IntegerDigits@x;
   Length@xd -
    Length@IntegerDigits@FromDigits@Reverse@xd, {1000}] // Timing

{0.029022, Null}

versus

Do[(xs = ToString[x];
    StringLength[xs] -
     StringLength[
      ToString[ToExpression[StringReverse[xs]]]]), {1000}] // Timing

{0.032321, Null}

Bobby

On Tue, 04 Oct 2011 17:19:44 -0500, Richard Fateman  
<fateman@eecs.berkeley.edu> wrote:

> On 10/4/2011 2:33 PM, DrMajorBob wrote:
>> I'm guessing that I got zero because I ran some of the code with an  
>> undefined x. My bad!
>
>
> I think that you (me too)  might not have noticed that one of my methods  
> changed x.  Here is a safer version.
>
> savedx= 24^24*55^55;
>
>
> Well, here's another method..
>
> (xs = ToString[savedx];
>   StringLength[xs] -    
> StringLength[ToString[ToExpression[StringReverse[xs]]]])
>
> Let's time it, running 1000 times.
>
> Do[ (xs = ToString[savedx];
>     StringLength[xs] -
>      StringLength[
>       ToString[ToExpression[StringReverse[xs]]]]), {1000}] // Timing
>
> {0.063,Null}
>
> This bizarre hack  is reasonably fast, indeed twice as fast  as your  
> method, on my system.
>
> Do[Replace[
>     IntegerDigits@x, {__, zeroes : 0 ..} :>
>      Length@{zeroes}], {1000}] // Timing
>
> {0.141, Null}
>
> and seven times as fast as my older simple arithmetic method which uses  
> iteration,
>
>
> Do[(n = 0; x = savedx; While[Mod[x, 10] == 0, (x = x/10; n++)];
>     n), {1000}] // Timing
>
> {0.438, Null}
>
> and which (as I contended) was inefficient in Mathematica.  While you  
> seem to think that this method is ancient and outmoded, I think it is  
> not the method, but the implementation of iteration. Or perhaps of  
> arithmetic?
>
> Another implementation of this arithmetical method on the same computer  
> takes 0.063 seconds.
>
> RJF
>
>>
>> Correcting that, I find the esoteric method faster than your ancient,  
>> outmoded ones:
>>
>> x = 24^24*55^55;
>> Replace[IntegerDigits@x, {__, zeroes : 0 ..} :>
>>    Length@{zeroes}] // Timing
>>
>> {0.000198, 55}
>>
>> (n = 0; While[GCD[x, 10^n] == 10^n, n++]; n - 1) // Timing
>>
>> {0.000417, 55}
>>
>> (n = 0; While[Mod[x, 10] == 0, (x = x/10; n++)]; n) // Timing
>>
>> {0.000228, 55}
>>
>> Bobby
>>
>> On Tue, 04 Oct 2011 15:57:30 -0500, Richard Fateman  
>> <fateman@eecs.berkeley.edu> wrote:
>>
>>> On 10/4/2011 9:44 AM, DrMajorBob wrote:
>>>> There's nothing "esoteric" about IntegerDigits, Replace, or Repeated,  
>>>> as in:
>>>>
>>>> x = 24^24*55^55;
>>>> Replace[IntegerDigits@x, {__, zeroes : 0 ..} :>
>>>>    Length@{zeroes}] // Timing
>>>>
>>>> {0.000185, 55}
>>>
>>> My feeling is that these ARE esoteric.  A person just introduced to  
>>> Mathematica would probably not encounter IntegerDigits, Repeated, or  
>>> patterns other than the trivial one used in pseudo function  
>>> definitions as
>>> f[x_]:=   x+1.
>>>
>>>
>>>>
>>>> If we wanted brute-force arithmetic, we might use Fortran.
>>>>
>>>> Your suggested solutions are NOT greatly hindered by "the slow  
>>>> implementation of looping constructs in Mathematica", on the other  
>>>> hand:
>>>>
>>>> (n = 0; While[GCD[x, 10^n] == 10^n, n++]; n - 1) // Timing
>>>>
>>>> {0.000029, 0}
>>>
>>> huh?   I got  {0., 55}.   Perhaps my computer is faster or has a lower  
>>> resolution timer, but we should both get 55.
>>>
>>>>
>>>> (n = 0; While[Mod[x, 10] == 0, (x = x/10; n++)]; n) // Timing
>>>>
>>>> {0.000018, 0}
>>>
>>> I mention the slow implementation of looping constructs simply to warn  
>>> people that if you can resolve your computation by simple composition  
>>> of built-in functions e.g. F[G[H[x]]]   and don't rely on Mathematica
>>> to efficiently execute loops written as While[] For[]  etc, you are  
>>> probably going to run faster.  Let Mathematica's operation on compound  
>>> objects like lists do the job.  Length[] is a lot faster than counting  
>>> with a While etc.
>>>
>>> In my timings, doing the operations 1000 times..
>>> Do[.....,{1000}]//Timing
>>>
>>> I found that my solutions were about 10X faster than the IntegerDigits  
>>> one, on this particular value of x.
>>>
>>> Fortran can't be used unless you manage arbitrary precision integers...
>>>
>>> RJF
>>>
>>>
>>>
>>
>>
>


-- 
DrMajorBob@yahoo.com

[toc] | [prev] | [standalone]


Back to top | Article view | comp.soft-sys.math.mathematica


csiph-web