Code to calculate

Cecil Westerhof

unread,

Apr 18, 2019, 6:59:08 AM4/18/19

to

I wrote a script to calculate the smallest numbers of a given
multiplicative persistence.¹ One proc I wrote is:
proc getMultPers {number} {
set multPers 0
while {[string length ${number}] > 1} {
incr multPers
set value 1
foreach {digit} [split ${number} {}] {
set value [* ${value} ${digit}]
}
set number ${value}
}
return ${multPers}
}

Can this be improved upon?

I write an article about the program this weekend. I think it shows a
few of the advantages of using Tcl. ;-)

1: https://en.wikipedia.org/wiki/Persistence_of_a_number#Smallest_numbers_of_a_given_multiplicative_persistence

--
Cecil Westerhof
Senior Software Engineer
LinkedIn: http://www.linkedin.com/in/cecilwesterhof

Arjen Markus

unread,

Apr 18, 2019, 7:32:10 AM4/18/19

to

Well, that is a "makkie":

proc getMultPers {number} {
foreach n $number {
incr multiplicity($n)
}

parray multiplicity

return [array get multiplicity]
}

foreach {n count} [getMultPers {1 2 3 3 4 1}] {
puts "$n: multiplicity = $count"
}

In fact, two solutions for the price of one :). parray will print the result to the screen in a nice alphabetical (in this case: numerical) order. The list that is returned is not sorted. That would take a bit of effort, but I leave that as an exercise.

Regards,

Arjen

heinrichmartin

unread,

Apr 18, 2019, 7:52:13 AM4/18/19

to

On Thursday, April 18, 2019 at 12:59:08 PM UTC+2, Cecil Westerhof wrote:

> I wrote a script to calculate the smallest numbers of a given
> multiplicative persistence.¹

Tcl's EIAS is definitely a benefit here, but note that this yields shimmering, which impacts performance. In other words: just because integer-number conversions are not explicitly coded, it does not mean they are not performed. The question is whether this back and forth is efficient.

> One proc I wrote is:
> proc getMultPers {number} {
> set multPers 0
> while {[string length ${number}] > 1} {

while {9 < $number}

> incr multPers
> set value 1
> foreach {digit} [split ${number} {}] {
> set value [* ${value} ${digit}]

note that not everybody imports ::tcl::mathop ...

> }
> set number ${value}

set number [::tcl::mathop::* {*}[split $number {}]]

> }
> return ${multPers}
> }
>
> Can this be improved upon?

What's the criterion? You mentioned "benefits of Tcl" - so I suggest showcasing.

proc getMultPers {number} {
# TODO reject negative numbers
for {set res 0} {9 < $number} {incr res} {
set number [::tcl::mathop::* {*}[split $number {}]]
}
return $res
}

This might even be more efficient than yours, but I have not benchmarked it.

heinrichmartin

unread,

Apr 18, 2019, 8:05:42 AM4/18/19

to

On Thursday, April 18, 2019 at 1:52:13 PM UTC+2, heinrichmartin wrote:
> # TODO reject negative numbers

# TODO and make sure that number has the correct string representation!
set number [expr {$number}] ;# fixes 0x42, but not 1e10

Btw, an initial check for digits zero might increase average performance.

Cecil Westerhof

unread,

Apr 18, 2019, 10:14:07 AM4/18/19

to

heinrichmartin <martin....@frequentis.com> writes:

> On Thursday, April 18, 2019 at 12:59:08 PM UTC+2, Cecil Westerhof wrote:
>> I wrote a script to calculate the smallest numbers of a given
>> multiplicative persistence.¹
>
> Tcl's EIAS is definitely a benefit here, but note that this yields
> shimmering, which impacts performance. In other words: just because
> integer-number conversions are not explicitly coded, it does not mean
> they are not performed. The question is whether this back and forth is
> efficient.
>
>> One proc I wrote is:
>> proc getMultPers {number} {
>> set multPers 0
>> while {[string length ${number}] > 1} {
>
> while {9 < $number}

I do not see a performance improvement, it could even be a little
slower. I find my code more clear, so for the moment I keep my code.
Normally I find clearness more important as efficiency. Only when code
becomes a lot faster, or needs a lot less memory I would use less
clear code.

>
>> incr multPers
>> set value 1
>> foreach {digit} [split ${number} {}] {
>> set value [* ${value} ${digit}]
>
> note that not everybody imports ::tcl::mathop ...

It is part of my program. But a good point.

>
>> }
>> set number ${value}
>
> set number [::tcl::mathop::* {*}[split $number {}]]

That is much more clear. Shows that it never hurts to let someone else
give a look.

>> Can this be improved upon?
>
> What's the criterion? You mentioned "benefits of Tcl" - so I suggest
> showcasing.

I should have mentioned those.
First I want code be clear.
Only after that I am interested in CPU or memory performance. Or the
benefit should be huge.

For example my program uses sort scan and generate.

Sort is the most clear, but scan is not much less clear and needs a
little more as 50% of the time.

But when I generate potential numbers the improvement is huge.
Immediately and long term.

With sort it is O(n log n), with scan O(n) and generate O(log n).
When calculating for ** 10 10 the needed time in minutes:
888
523
1 SECOND

With generate ** 10 25 takes 22 minutes. The other two I did not run
beyond ** 10 10. ;-)

> proc getMultPers {number} {
> # TODO reject negative numbers

I generate the numbers, so in this case I do not need to check them.

> for {set res 0} {9 < $number} {incr res} {
> set number [::tcl::mathop::* {*}[split $number {}]]
> }
> return $res
> }
>
> This might even be more efficient than yours, but I have not
> benchmarked it.

The performance is about the same, but I find this solution more
elegant.

Cecil Westerhof

unread,

Apr 18, 2019, 10:44:05 AM4/18/19

to

I do a check before I call the proc, so no numbers that contain a zero
are used when calling the proc.

I should have given a bit more background information.