HP Forums
(49G) Power of a Permutation - Printable Version

+- HP Forums (https://www.hpmuseum.org/forum)
+-- Forum: HP Software Libraries (/forum-10.html)
+--- Forum: General Software Library (/forum-13.html)
+--- Thread: (49G) Power of a Permutation (/thread-4015.html)



(49G) Power of a Permutation - Gerald H - 05-29-2015 11:15 AM

Given a valid permutation the programme calculates the integer power.

eg For input

{ 1 88 40 96 102 95 14 55 25 60 37 46 89 21 29 91 90 2 69 80 85 97 83 28 3 50 13 74 92 71 42 58 75 73 4 31 53 63 87 59 56 6 100 26 41 77 35 84 9 43 39 8 62 106 19 67 11 5 12 93 52 82 47 70 61 18 86 78 16 17 105 38 27 22 10 24 79 104 57 94 33 15 36 65 49 32 34 103 76 54 44 20 48 51 101 7 81 66 30 72 23 98 64 68 99 45 }

1000001

the programme returns

{ 1 103 43 8 98 95 19 24 26 39 96 38 37 69 49 97 54 88 74 3 16 92 83 82 50 75 11 15 9 71 42 5 94 79 52 31 7 84 46 100 67 6 60 33 56 63 61 73 44 10 12 76 14 45 28 86 4 102 72 87 89 21 65 17 13 2 32 104 22 90 105 48 57 29 51 62 47 68 35 40 80 85 36 27 91 58 77 64 53 106 81 25 34 59 101 55 20 18 30 93 23 66 70 78 99 41 }

in 77 sec on the 49G & on the 50G in 10.7 sec.

A surprisingly large time differential!

Code:

::
  CK2&Dispatch
  # FF
  ::
    SWAP
    FPTR 7 17B
    SWAP
    FPTR2 ^DupZIsNeg?
    IT
    ::
      SWAPDUP
      toLEN_DO
      DUPINDEX@
      NTHCOMPDROP
      INDEX@
      FPTR2 ^#>Z
      SWAP
      FPTR2 ^Z2BIN
      4ROLL
      PUTLIST
      SWAPLOOP
      DROPSWAP
      FPTR2 ^ZAbs
    ;
    DUP
    FPTR2 ^QIsZero?
    case
    ::
      DROP
      LENCOMP
      ID x00D
    ;
    FPTR2 ^DupZIsOne?
    caseDROP
    OVERUNROT
    FPTR2 ^Z>ZH
    FPTR2 ^ZBits
    #1-
    ZERO_DO
    SWAPDUP
    FPTR 7 17C
    SWAP
    ISTOP-INDEX
    #1-
    FPTR2 ^ZBit?
    IT
    ::
      SWAP3PICK
      FPTR 7 17C
      SWAP
    ;
    LOOP
    DROPSWAPDROP
  ;
;