Mini-challenge: MAX(factors of 2 or 5)

[Joe Horn]

This mini-challenge is really is a cry for help improving a painfully inelegant-looking routine.

Suppose an integer X contains prime factors of 2^Y and 5^Z. What is MAX(Y,Z)?

Example: 2000 = 2^4 * 5^3, so Y=4 and Z=3, so MAX(Y,Z)=4.

The following ugly HP 50g routine takes X as its input and outputs MAX(Y,Z):

Code:

<< FACTORS DUPDUP
IF 2 POS DUP THEN 1. + GET ELSE NIP END SWAP DUP
IF 5 POS DUP THEN 1. + GET ELSE NIP END MAX >>

Input: 31250 (which = 2*5^6)
Output: 6 in 0.114 seconds

Input: 2^555
Output: 555 in 0.97 seconds

Input: 3^175
Output: 0 in 0.87 seconds

It works and it's fast enough, but it looks like a brutally hamfisted approach. It hurts my eyes. There MUST be a simple and elegant way of doing this. Thanks for any insights you can share!

[3298]

The first thing that comes to mind is that the FACTORS output looks made for the SysRPL command Lookup. (For those not familiar with it, the command compares a given object with the first, third, etc. entry in a given list, returning the object after the first match.) Then maybe MAP or something similar to get rid of the code duplication... but that has some stack protection, so the FACTORS output has to be smuggled inside somehow. Let's use >HCOMP for that, a list doesn't change when eval'ed.
Resulting code:

Code:

::
  xFACTORS
  { Z2_ Z5_ }
  ' ::
    ' EQUAL SWAP Lookup
    NOT_IT DROP%0_
  ;
  ROT >HCOMP
  FPTR2 ^SECOEXEC (this is xMAP's internal part)
  INCOMPDROP %MAX
;

The speed is pretty much the same as your code, the biggest time sink is most likely FACTORS anyway. 59 bytes, checksum #FF3E.

[Claudio L.]

(01-16-2018 10:52 PM)Joe Horn Wrote:  There MUST be a simple and elegant way of doing this. Thanks for any insights you can share!

I would approach it based on the last digit:

if Z=Y+C, then:

2^Y*5^Z = 10^Y*5^C
or if there's more 2's:
Y=Z+D

2^Y*5^Z = 10^Z*2^D

In other words: The common amount of 2's and 5's is the number of trailing zeros. Trimming and counting the trailing zeros is the first step.
Once that's done, the resulting number is either 2^D or 5^C, so if the last digit is a 5, then divide by 5 until 1 while counting, or faster: from 1, multiply by 5 while counting until >= value. For large C it might be faster to use C=LN(5^C)/LN(5)
If the last digit is not 5, then it has to be a power of 2, and the same reasoning as before works D=LN(2^D)/LN(2).

[Thomas Okken]

My implementation of Claudio's approach:

Code:

<< 0 UNROT
  WHILE DUP2 MOD NOT
  REPEAT ROT 1 + UNROT / LASTARG SWAP DROP
  END DROP SWAP
>>

'NDIVS' STO

This takes a number N in level 2 and a factor F in level 1, and returns the number M of times that F divides N in level 1, and N / F^M in level 2, and...

Code:

<< 10 NDIVS SWAP DUP 2 NDIVS
  IF DUP NOT
  THEN DROP 5 NDIVS
  END UNROT DROP2 +
>>

...takes a number in level 1 and returns the desired result in level 1.

I'm a bit conflicted about this challenge because what's mathematically elegant and what's RPL-ically elegant are probably quite different. Claudio's approach is mathematically much better than using the FACTORS function -- why find the complete prime factorization when all you want is the multiplicity of two specific factors? And what about memory usage? Also, the FACTORS approach fails if the factors you're looking at happen not to be primes.

[Gerald H]

User & Sys suggestions:

Code:

« 0 SWAP
  WHILE DUP 2 IDIV2
0 SAME
  REPEAT NIP SWAP 1
+ SWAP
  END DROP 0 SWAP
  WHILE DUP 5 IDIV2
0 SAME
  REPEAT NIP SWAP 1
+ SWAP
  END DROP2 MAX
»

Code:

::
  CK1&Dispatch
  # FF
  ::
    FPTR2 ^ZTrialDiv2
    BINT0
    ROT
    BEGIN
    DUP
    ZINT 5
    FPTR2 ^ZDIVext
    ZINT 0
    EQUAL
    WHILE
    ::
      SWAPDROP
      SWAP#1+SWAP
    ;
    REPEAT
    2DROP
    #MAX
    FPTR2 ^#>Z
  ;
;

[Joe Horn]

(01-17-2018 04:49 AM)Thomas Okken Wrote:  I'm a bit conflicted about this challenge because what's mathematically elegant and what's RPL-ically elegant are probably quite different.

Quite right. Several brute-force routines have been suggested, performing trial divisions one at a time and counting them. This works but is terribly slow for large inputs. For example, Gerald's User RPL program takes 25 times longer than mine (in the OP) on an input of 10^50 (exact integer). This is no doubt because looping in User RPL is much slower than the FACTORS command.

Quote:... why find the complete prime factorization when all you want is the multiplicity of two specific factors? ... Also, the FACTORS approach fails if the factors you're looking at happen not to be primes.

Agreed. FACTORS is pretty fast, but it's overkill, and fails if you're looking for composites. But brute-force looping and tallying trial divisions is terribly slow. Isn't there a way to avoid all that looping?

Here's one idea that's haunting me: Instead of doing MOD(X, 2) repeatedly, how about doing GCD(X, 2^10) repeatedly? That could be used to chop off 10 powers of 2 at a time (until none are left), instead of just one at a time.

It's reminiscent of the old 'COTENS' program ('Cast Out TENS') which takes any integer and discards any factors of 2 or 5 from it:

<< WHILE DUP 1000000000000 GCD DUP 1 > REPEAT / END DROP >>

Example:
Input: 1500000000000000000
Output: 3

It's very fast because it discards up to twelve 2's and up to twelve 5's in every iteration. But I'm not sure how to tally the factors.

Darn... my brain just ran out of caffeine and I must go to bed.

[pier4r]

question. Is the input always a number with factors of 2 and/or 5 ? Or can it be whathever number?

[Joe Horn]

(01-19-2018 12:43 PM)pier4r Wrote:  question. Is the input always a number with factors of 2 and/or 5 ? Or can it be whathever number?

It can be any positive integer. If it has no factors of 2 or 5, then the output of the desired routine should be 0.

[pier4r]

Then I don't see why checking through division it is "unelegant".

I mean it is like a fizzbuzz problem, with a generic input (although restricted to integers) there is not much to do.

it is still unclear to me what happens when there is only 2, as in 32, or only 5, as in 625. It is a multiplicity of 0 for one factor still valid?

(Sorry I did not yet decode the code previously posted)

[Thomas Okken]

(01-19-2018 02:10 PM)pier4r Wrote:  Then I don't see why checking through division it is "unelegant".

I think Joe meant "slow." The problem with RPL, apparently, is that executing it is so slow that even a heavyweight primitive like FACTORS can outperform a mathematically more efficient user code algorithm.

(01-19-2018 02:10 PM)pier4r Wrote:  it is still unclear to me what happens when there is only 2, as in 32, or only 5, as in 625. It is a multiplicity of 0 for one factor still valid?

Jeez, what is it with people and their phobia of multiplicity zero? It's like those people who are always saying that 0! = 1 is some "weird special case." Drives me nuts! /rant
For 32, your program should return 5, because 32 = 2^5 * 5^0, and max(5, 0) = 5. By the same logic, the result for 625 should be 4.

[pier4r]

(01-19-2018 02:40 PM)Thomas Okken Wrote:  [

Jeez, what is it with people and their phobia of multiplicity zero? It's like those people who are always saying that 0! = 1 is some "weird special case." Drives me nuts! /rant
For 32, your program should return 5, because 32 = 2^5 * 5^0, and max(5, 0) = 5. By the same logic, the result for 625 should be 4.

Well yes, now that I see it, it is a MAX function. Somehow I was stuck that the number either contained both factors or it was invalid.

For the FACTORS vs division part, well I guess I overlooked parts of the discussion I did not get that FACTORS is much faster than a normal division in RPL.

[Joe Horn]

(01-19-2018 02:40 PM)Thomas Okken Wrote:  

(01-19-2018 02:10 PM)pier4r Wrote:  Then I don't see why checking through division it is "unelegant".

I think Joe meant "slow."

Yes, plus the fact that it's the obvious brute-force way of doing it. It doesn't use any number theory tricks, or clever shortcuts, or anything which represents thinking outside the box... something that you see in somebody else's code and you say "Wow, that's cool!" ... you know, something elegant, as it were.

Brilliant Analogy: Imagine that I have a HUGE barrel containing a zillion American coins. I want to know how many pennies and nickels are in the barrel. My original FACTORS method above is analogous to pouring the entire barrel's contents into a very fast coin counting machine, which would count ALL the types of coins. That's fast and easy, but it's functional overkill, because it also counts the dimes, quarters, half dollars, and dollars.

On the other hand, the brute-force division methods above is analogous to spreading all the pennies out on the floor, looking for pennies, and counting as you remove them from the floor. Then, when that's done, do the same for the nickels. That has the benefit of not spending time counting the unwanted coins. But it's totally not elegant; it's just brute-force counting.

My suggested trick (GCD with 2^10 and 5^10) is analogous to grabbing handfuls of ten pennies at a time... and then counting the last handful which is less than 10. It's better than counting them all 1 at a time. But how much more elegant is counting handfuls instead of counting coins? Ah, my quest for a number theory trick continues....

[Thomas Okken]

(01-19-2018 07:39 PM)Joe Horn Wrote:  

(01-19-2018 02:40 PM)Thomas Okken Wrote:  I think Joe meant "slow."

Yes, plus the fact that it's the obvious brute-force way of doing it. It doesn't use any number theory tricks, or clever shortcuts, or anything which represents thinking outside the box...

You're using a rather more exalted version of "elegant" than I do. I think the repeated division is more elegant than FACTORS because it doesn't do all the unnecessary work of finding all those other factors that you aren't even interested in.

Also, the GCD trick isn't that much better, because calculating a GCD still requires repeated division, though admittedly not as many (I think it is usually better, and never worse (*)).

To really cut down on the divisions, you should divide by high powers of the desired factors, and back off toward lower factors when the higher ones don't divide the number evenly any more. That would be fast; whether it would be elegant is a matter of taste. Also it might not even be beneficial: a lot of complexity analysis ignores how the cost of doing arithmetic becomes higher when you're realing with larger numbers. Dividing by 512 is harder than dividing by 2.

(*) For example, finding the factors of 2 in 1e9 by taking its GCD with 2^16, using Euclid's algorithm, takes 6 divisions, while basic repeated division takes 10 divisions. How to quickly determine that that GCD, 512, equals 2^9 is left as an exercise to the reader.

[DavidM]

While I can appreciate your desire for a less brutish approach, Joe, I think it's going to be difficult to outperform your original method with standard RPL. FACTORS admittedly does more than is needed, but its speed makes it an attractive command to utilize here.

Just for something different, here's an alternative approach that still uses FACTORS, and what it lacks in elegance is more than made up for in obfuscation :

Code:

\<<
  DUP
  {
    30 *
    FACTORS
    REVLIST
    1 5 SUB LIST\-> ROLLD
    DROP2 DROP
    MAX 1 -
  }
  IFT
\>>

Slightly slower than your original method, and still just parses the FACTORS list to get the needed values. It is a bit smaller, though. Could be even shorter if 0 doesn't need to be considered for input.

Personally, I don't see anything wrong with your initial approach. It is much clearer than the above monster, and that (to me) is far more valuable than the few bytes saved.

[Claudio L.]

(01-19-2018 08:15 PM)Thomas Okken Wrote:  Also, the GCD trick isn't that much better, because calculating a GCD still requires repeated division, though admittedly not as many (I think it is usually better, and never worse (*)).

Not really, the algorithm can be done by subtraction only, which works quite well when the numbers are of similar magnitude happens to be this case.

(01-19-2018 08:15 PM)Thomas Okken Wrote:  (*) For example, finding the factors of 2 in 1e9 by taking its GCD with 2^16, using Euclid's algorithm, takes 6 divisions, while basic repeated division takes 10 divisions. How to quickly determine that that GCD, 512, equals 2^9 is left as an exercise to the reader.

Why 2^16? It doesn't guarantee you'll find the maximum if you don't know that the result is 9. You would in this case use 2^32 which is > 1e9 and therefore is guaranteed to have more 2's than needed.
Doing the GCD of 2^32 with 1e9 requires 56 subtractions (more or less, I might have messed up the count at some point). In a CPU without hardware division, this is faster than doing the divisions.

I cooked up a quick factor extractor:

Code:


«
  → 
    'X' 'FCTR' 
   « FCTR WHILE DUP X < REPEAT SQ END
    X GCD X OVER / 
  »
»

It takes a number and the prime factor you want to extract, returns the prime factor extracted with its exponent, and what's left of the number, in your example:
1e9 2 ====> 512 1953125
where it's easy to see multiplying the 2 values you have to get the original 1e9.
The first part looks for a power that is guaranteed to have enough times the factor, so the GCD can extract all of them in one shot. It uses SQ so it reaches a value relatively fast, but can overshoot, causing more delay in the GCD.
The only caveat is that if the given factor is not prime, the GCD will not necessarily be a power of the given factor, but some mix of powers of its prime factors.

EDIT: The code above uses only 1 GCD (many subtractions), 1 division and log2(N) multiplications.

[pier4r]

(01-19-2018 07:39 PM)Joe Horn Wrote:  Yes, plus the fact that it's the obvious brute-force way of doing it. It doesn't use any number theory tricks, or clever shortcuts, or anything which represents thinking outside the box... something that you see in somebody else's code and you say "Wow, that's cool!" ... you know, something elegant, as it were.

I am unconvinced that "elegant", as in "short and to the point" for how I understood your analogy, is always valid. Or better could be that the elegant procedure is perceived elegant only because it hides complexity.

Whatever elegant procedure in mathematics mostly ends up being addition, subtractions, multiplications and division (the last two are already a composition of the first two). So better than a division is hard to get. (aside from optimizations in this or that language)

Sure you may have the function F(z) that is all fancy, but behind F(z) mostly there are the four functions arranged somehow.

Once again, this looks to me like a fizzbuzz problem. The most that I can see is accelerated division (still division).
Like:

- given a number
- compute what could be a number made out of power of two with similar magnitude of the given number. Divide the given number by this number. If the result is not a whole, half the exponent of the power of two and try again (like binary search).
- Same for power of 5.

At the end it may be an (apparent) faster search of the exponents, but the straight division would be faster I would bet.

Another way is to apply the simple division but for increasing power.

- Given X
- divide X by 2. If the reminder is 0, divide it by 4. If the reminder is 0, divide it by 8. Etc.. If it fails, try again with 2 and so on.
- Same by 5.

Still, at the end is the same procedure, just with "hidden" divisions.


It is a bit like: what is more elegant: 1.414213.... or the continued fraction [1; 2, 2, 2, 2, 2, 2 ...] to identify square root of 2?

Some would say the square fraction, because it looks powerful and complicated.
Some others would say the decimal expansion, because it is the result of the complicated continued fraction that therefore is not needed.

It depends on what one wants to optimize.

[Joe Horn]

(01-19-2018 11:48 PM)pier4r Wrote:  Once again, this looks to me like a fizzbuzz problem.

Not knowing what that meant, I looked it up and found this:

Quote:The "Fizz-Buzz test" is an interview question designed to help filter out the 99.5% of programming job candidates who can't seem to program their way out of a wet paper bag. The text of the programming assignment is as follows:

"Write a program that prints the numbers from 1 to 100. But for multiples of three print “Fizz” instead of the number and for the multiples of five print “Buzz”. For numbers which are multiples of both three and five print “FizzBuzz”."

Please be aware that MAX(factors of 2 or 5) is actually needed for an actual programming task, namely, printing integer ratios as repeating decimals. MAX(denominator's factors of 2 or 5) yields the number of digits after the decimal point which do NOT repeat. So this isn't just a fizzbuzz problem... unless you mean something else by "a fizzbuzz problem" in which case please elucidate.

[Gerald H]

You could use the programme below. XdYB can be found here:

http://www.hpmuseum.org/forum/thread-400...l#pid36366

Code:

« 1 SWAP 7 * 10
XdYB DTAG DUP "°"
POS SWAP "." POS -
1 -
»

[Thomas Okken]

(01-20-2018 04:21 AM)Joe Horn Wrote:  Please be aware that MAX(factors of 2 or 5) is actually needed for an actual programming task, namely, printing integer ratios as repeating decimals. MAX(denominator's factors of 2 or 5) yields the number of digits after the decimal point which do NOT repeat.

That makes it a not very interesting task (*), though, because printing numbers is something you only have to do fast enough for humans to keep up with, which is many orders of magnitude removed from the requirements of industrial-scale number crunching.

I noticed several years ago that the glibc version of printf(3) will print binary floating-point numbers at full precision, in decimal, and that it actually contains arbitrary-precision math logic to allow it to do that. It seemed crazy to me when I first saw that code, but it made more sense once I realized that it doesn't have to do all that usually, when people are looking for numbers with maybe 5 digits, and basically never while the computer is doing hard-core number crunching.

(*) Not very interesting from my point of view, anyway.

[Paul Dale]

The 34S might be able to do this faster: extract the exponent from the real which is the number of factors of ten present after the decimal position is adjusted for. Log₁₀ of the mantissa should give the number of digits to adjust. Finally, take out the factors of 2 or 5 that remain.


Pauli