Minichallenge: MAX(factors of 2 or 5)

01162018, 10:52 PM
Post: #1




Minichallenge: MAX(factors of 2 or 5)
This minichallenge is really is a cry for help improving a painfully inelegantlooking 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 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! <0ɸ0> Joe 

01172018, 01:36 AM
Post: #2




RE: Minichallenge: MAX(factors of 2 or 5)
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: :: 

01172018, 04:03 AM
Post: #3




RE: Minichallenge: MAX(factors of 2 or 5)
(01162018 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). 

01172018, 04:49 AM
Post: #4




RE: Minichallenge: MAX(factors of 2 or 5)
My implementation of Claudio's approach:
Code: << 0 UNROT 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 ...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 RPLically 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. 

01172018, 06:13 AM
(This post was last modified: 01172018 06:26 AM by Gerald H.)
Post: #5




RE: Minichallenge: MAX(factors of 2 or 5)
User & Sys suggestions:
Code: « 0 SWAP Code: :: 

01192018, 07:20 AM
Post: #6




RE: Minichallenge: MAX(factors of 2 or 5)
(01172018 04:49 AM)Thomas Okken Wrote: I'm a bit conflicted about this challenge because what's mathematically elegant and what's RPLically elegant are probably quite different. Quite right. Several bruteforce 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 bruteforce 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. <0ɸ0> Joe 

01192018, 12:43 PM
Post: #7




RE: Minichallenge: MAX(factors of 2 or 5)
question. Is the input always a number with factors of 2 and/or 5 ? Or can it be whathever number?
Wikis are great, Contribute :) 

01192018, 01:51 PM
Post: #8




RE: Minichallenge: MAX(factors of 2 or 5)
(01192018 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. <0ɸ0> Joe 

01192018, 02:10 PM
Post: #9




RE: Minichallenge: MAX(factors of 2 or 5)
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) Wikis are great, Contribute :) 

01192018, 02:40 PM
Post: #10




RE: Minichallenge: MAX(factors of 2 or 5)
(01192018 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. (01192018 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. 

01192018, 05:51 PM
Post: #11




RE: Minichallenge: MAX(factors of 2 or 5)
(01192018 02:40 PM)Thomas Okken Wrote: [ 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. Wikis are great, Contribute :) 

01192018, 07:39 PM
Post: #12




RE: Minichallenge: MAX(factors of 2 or 5)
(01192018 02:40 PM)Thomas Okken Wrote:(01192018 02:10 PM)pier4r Wrote: Then I don't see why checking through division it is "unelegant". Yes, plus the fact that it's the obvious bruteforce 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 bruteforce 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 bruteforce 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.... <0ɸ0> Joe 

01192018, 08:15 PM
Post: #13




RE: Minichallenge: MAX(factors of 2 or 5)
(01192018 07:39 PM)Joe Horn Wrote:(01192018 02:40 PM)Thomas Okken Wrote: I think Joe meant "slow." 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. 

01192018, 10:38 PM
Post: #14




RE: Minichallenge: MAX(factors of 2 or 5)
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: \<< 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. 

01192018, 10:48 PM
(This post was last modified: 01192018 10:53 PM by Claudio L..)
Post: #15




RE: Minichallenge: MAX(factors of 2 or 5)
(01192018 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. (01192018 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:
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. 

01192018, 11:48 PM
(This post was last modified: 01192018 11:50 PM by pier4r.)
Post: #16




RE: Minichallenge: MAX(factors of 2 or 5)
(01192018 07:39 PM)Joe Horn Wrote: Yes, plus the fact that it's the obvious bruteforce 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. Wikis are great, Contribute :) 

01202018, 04:21 AM
Post: #17




RE: Minichallenge: MAX(factors of 2 or 5)
(01192018 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 "FizzBuzz 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: 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. <0ɸ0> Joe 

01202018, 06:04 AM
Post: #18




RE: Minichallenge: MAX(factors of 2 or 5)
You could use the programme below. XdYB can be found here:
http://www.hpmuseum.org/forum/thread400...l#pid36366 Code: « 1 SWAP 7 * 10 

01202018, 08:18 AM
(This post was last modified: 01202018 08:23 AM by Thomas Okken.)
Post: #19




RE: Minichallenge: MAX(factors of 2 or 5)
(01202018 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 industrialscale number crunching. I noticed several years ago that the glibc version of printf(3) will print binary floatingpoint numbers at full precision, in decimal, and that it actually contains arbitraryprecision 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 hardcore number crunching. (*) Not very interesting from my point of view, anyway. 

01202018, 09:40 AM
Post: #20




RE: Minichallenge: MAX(factors of 2 or 5)
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_{10} of the mantissa should give the number of digits to adjust. Finally, take out the factors of 2 or 5 that remain.
Pauli 

« Next Oldest  Next Newest »

User(s) browsing this thread: 1 Guest(s)