Prime factorization in the 48GX



#10

Hi everybody,

Does the 48GX have an indigenous function for generating the prime factors of a number? I have scoured the users guide and have found no mention of this capability, so my premonition is that the answer will be no. I did work up a routine for my 67 that would do prime factors some time back...I supose I could convert it to RPL and use that...unless somebody knows of a nice existing program somewhere on the web...

My RPL fluency is somewhat lacking...this would be good training I suppose.

Thanks, Hal


#11

http://www.hpcalc.org and search for factorization, there are a few programs available.


#12

My 48SX came with several handy programs built-in in the VAR menu.

One of them is SJTRI, which quite quickly gives you the prime factors.

In addition it also gives another line which I don't understand,
Example: 456 factorizes as 2 2 2 3 19, the additional line says .364013671875. Any idea what this means?


#13

My IDENTIFY program for the HP-71B identifies your value, .364013671875, as being exactly 1491/4096, so it probably is the timing, i.e., the time in seconds it took the program to run.

Best regards from V.


#14

Valentin,

IDENTIFY truely is a great program of yours. You seem to have some more inspiration that lets you conclude "seconds". Would you share what gave you that thought? Is the 48G doing 4096 operations per second?


#15

Hi, George:

George posted:

    "IDENTIFY truely is a great program of yours."

      Thank you very much. It's certainly handy at times to try and recognize how some particular numeric value came to be.

    "You seem to have some more inspiration that lets you conclude "seconds". Would you share what gave you that
    thought? Is the 48G doing 4096 operations per second?"

      No idea. I know next to nothing re the 48G, but I seem to remember that somewhere I read its clock issues 4096 "ticks" per second, i.e., it's user-accessible time unit is defined to be 1/4096-th of a second, so that number at the end of the factorization being a multiple of 1/4096 would seem to indicate it's actually an elapsed time.

Best regards from V.


#16

Quote:
...somewhere I read its clock issues 4096 "ticks" per second..

Valentin,

you remembered almost right:

Quote:
Since there are 8192 ticks in a second,

which is a quote from here.

So, as 2982/8192 is 1491/4096 to which your program conveniently reduced the result, you might have a valid point in suggesting it to be the time ticks.

Edited: 27 June 2008, 11:00 a.m.

#17

Quote:
...unless somebody knows of a nice existing program somewhere on the web...

The fastest RPL program I know was written by Joe Horn (
http://www.hpcalc.org/details.php?id=1582). As I prefer prime factors in algebraic form rather than in a list, I added the L2A routine, which does the job. On my HP-28S it takes about 51 seconds to factor 123456789: '3^2*3607*3803'. More in this thread.

Regards,

Gerson.

--------------------------------------------------

%%HP: T(3)A(D)F(.);
DIR
PF
\<< { } SWAP
DO NP ROT OVER +
ROT ROT / DUP
UNTIL 1 ==
END DROP L2A
\>>
NP
\<< DUP \v/ \-> s
\<< DUP
IF 2 MOD
THEN 3
WHILE DUP2 MOD
OVER s < AND
REPEAT 2 +
END DUP s
IF >
THEN DROP DUP
END
ELSE 2
END
\>>
\>>
L2A
\<< DUP SIZE 1 \=/
IF
THEN DUP 1 GET 1
\->LIST 1 ROT DUP SIZE
1 - 1 SWAP
FOR i DUP i GETI
ROT ROT GET OVER ==
IF
THEN DROP SWAP
1 + SWAP
ELSE DROP ROT
ROT 1 \->LIST + SWAP
DUP i 1 + GET 1
\->LIST ROT SWAP + 1
ROT
END
NEXT DROP 1
\->LIST + "'" SWAP DUP
SIZE 1 - 1 SWAP
FOR i DUP i GETI
ROT ROT GET SWAP
\->STR SWAP DUP 1 \=/
IF
THEN \->STR "^"
SWAP + +
ELSE DROP
END "*" + ROT
SWAP + SWAP 2
STEP DROP DUP
DUP SIZE 1 - 1 SWAP
SUB "'" + STR\-> SWAP
DROP
ELSE LIST\-> DROP
END
\>>


#18

Mark Adler's FACNUM (on Goodies Disk #2) is twice as fast as my HP48 factorizer. Its listing follows, with Mark's comments.

%%HP: T(3)A(R)F(.);
@ by Mark Adler
@ FACNUM (BYTES = 277.5, #74FFh)
@ Given an integer, return its prime factorization as a list.
@ For example, 16353 FACNUM returns { 3 3 23 79 }.
\<<
@ initialize factor list
{ } SWAP

@ For this part of the program the stack is: n factorlist, where the two are
@ kept so that the product of the list times n is the original integer.

@ factor out 2's
WHILE DUP 2 MOD NOT REPEAT
2 / SWAP 2 + SWAP END

@ factor out 3's
WHILE DUP 3 MOD NOT REPEAT
3 / SWAP 3 + SWAP END

@ start factor search at 5
5

@ The stack is now: k n factorlist, where the second two are maintained as
@ before, and k is the largest 5 mod 6 integer less than or equal to the
@ last factor found (execpt initially when it is set to 5).

@ search from k to sqrt(n) for factors---k must be 5 mod 6
WHILE OVER 1 \=/ REPEAT @ do while n is not one
OVER \v/ FLOOR @ go up to the floor of the square root
IFERR @ (divide by zero used as a loop breaker)
FOR i @ look at factors that are 1 and 5 mod 6
IF DUP i MOD NOT THEN
i 0 / END @ if 5 mod 6 divides n, then cause error
IF DUP i 2 + MOD NOT THEN
i 2 + 0 / END @ if 1 mod 6 divides n, then cause error
6 STEP
THEN DROP @ got an error---trash the zero
ELSE DUP @ end of loop---n divides n
END @ after this, stack is: factor n factorlist
ROT OVER + ROT ROT @ add factor to list (factor n factorlist')
SWAP OVER / SWAP @ divide out divisor (factor n' factorlist')
DUP 6 MOD 5 - 2 / + @ set k' to largest 5 mod 6 <= divisor
END @ find next factor (k' n' factorlist')

@ return list, dropping n and k
DROP2
\>>

If you want REALLY fast factorizing on the HP48, you'll have to go beyond User RPL. The best one ever written (I think) is Klaus Kalb's "FCTR" on Goodies Disk #8, in the MATH directory. It is very fast, though not as fast as FACTOR in the HP 50g, of course.

-Joe-


Possibly Related Threads...
Thread Author Replies Views Last Post
  Dangerous factorization Juraj O. 2 352 01-10-2013, 03:14 AM
Last Post: Angel Martin
  Prime Factorization for the HP15c? JamesT 2 372 09-29-2011, 10:29 AM
Last Post: JamesT
  hp48, factorization Sok-khieng Chum Hun 15 1,239 03-05-2010, 05:34 AM
Last Post: Hal Bitton in Boise

Forum Jump: