Post Reply 
(49G & 50g) Faster GCD for Integers
10-16-2017, 05:15 PM (This post was last modified: 10-18-2017 01:48 PM by Gerald H.)
Post: #1
(49G & 50g) Faster GCD for Integers
Edit: This programme is for the 49G, not the 50g. Sorry for the wrong indication.

For input two integers the programme returns the GCF, the programme is faster for integers of size (Edit: 1194 hex digits, ie 4500 dec digits) & greater, for smaller input the programme uses the inbuilt GCD.

Size: 191.

CkSum: # 2A81h

Code:
::
  CK2&Dispatch
  # FFFF
  ::
    2DUP
    FPTR2 ^ZNMin
    LENHXS
    # 1195
    #<case
    FPTR2 ^ZGCDext
    FPTR2 ^ZAbs
    SWAP
    FPTR2 ^ZAbs
    2DUP
    Z<
    ?SWAP
    FPTR2 ^DupQIsZero?
    caseDROP
    DUPUNROT
    FPTR2 ^ZMod
    FPTR2 ^DupQIsZero?
    caseDROP
    SWAP
    FPTR2 ^ZTrialDiv2
    ROT
    FPTR2 ^ZTrialDiv2
    ROT
    #MIN
    ZINT 2
    SWAP
    FPTR2 ^PPow#
    3UNROLL
    BEGIN
    2DUP
    FPTR2 ^RSUBext
    FPTR2 ^ZTrialDiv2
    #0<>
    WHILE
    ::
      FPTR2 ^DupZIsNeg?
      case
      ::
        SWAPDROP
        FPTR2 ^RNEGext
      ;
      ROTDROPSWAP
    ;
    REPEAT
    2DROP
    FPTR2 ^RMULText
  ;
;
Find all posts by this user
Quote this message in a reply
10-18-2017, 11:58 AM (This post was last modified: 10-18-2017 01:48 PM by Gerald H.)
Post: #2
RE: (49G & 50g) Faster GCD for Integers
A slightly improved programme for the 49G, crossover point is now for input of over 2000 digits.

The programme is good for the 50g, cross over point should be changed to 4000 digits.


Size: 191.0000

CkSum: # 951Ah

Code:
::
  CK2&Dispatch
  # FFFF
  ::
    2DUP
    FPTR2 ^ZNMin
    LENHXS
    # 7D0  (or # FA0 on the 50g)
    #<case
    FPTR2 ^ZGCDext
    FPTR2 ^ZAbs
    SWAP
    FPTR2 ^ZAbs
    2DUP
    Z<
    ?SWAP
    FPTR2 ^DupQIsZero?
    caseDROP
    DUPUNROT
    FPTR2 ^ZMod
    FPTR2 ^DupQIsZero?
    caseDROP
    SWAP
    FPTR2 ^ZTrialDiv2
    ROT
    FPTR2 ^ZTrialDiv2
    ROT
    #MIN
    3UNROLL
    BEGIN
    2DUP
    FPTR2 ^RSUBext
    FPTR2 ^ZTrialDiv2
    #0<>
    WHILE
    ::
      FPTR2 ^DupZIsNeg?
      case
      ::
        SWAPDROP
        FPTR2 ^ZAbs
      ;
      ROTDROP
    ;
    REPEAT
    2DROP
    ZINT 2
    ROT
    FPTR2 ^RP#
    FPTR2 ^RMULText
  ;
;
Find all posts by this user
Quote this message in a reply
Post Reply 




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