(50g) OEIS A028842: Product of Digits is a Prime

[Joe Horn]

(09-05-2017 02:43 PM)Gerald H Wrote:  I am particularly unhappy with this

4. OVER
WHILE DUP2 <
REPEAT OVER -
SWAP 4. + SWAP
END

section of code & would welcome a speedier method of calculating the 2 numbers deposited on the stack.

For input X, it returns two numbers A and B. An algorithm that generates A from X is this:

2. / √ 0 RND 4 *

Its accuracy is limited by its use of real square roots. Rewriting it for integer accuracy, and generating B from X and A, are left as exercises for the student.

EDIT: I wrote that because I was having a devil of a time figuring out how to do it! It finally dawned on me after staring at the numbers long enough. Here's a routine that inputs X and outputs X, A, B:

Code:

DUP 2. / √ DUP 0. RND 4. * SWAP .5 + FP OVER * CEIL

The bigger the input, the larger the speed difference. For an input of 1E7, the loop takes 11 seconds, and the direct approach takes 0.022 seconds, 500 times faster.

EDIT 2: Due to roundoff errors, this routine gets incorrect results for large inputs. Don't trust the output for inputs > 1E11. It seems to be ok for anything smaller than that.