2218.sagews

# The Fast Exponentiation Algorithm
# Input any exponent n, and trace how x^n is computed


# Get the exponent
n = 45237580360185018756081756013856

# This will serve as the base
prod = x

# Echo it back
print "The input value is", n

The input value is 45237580360185018756081756013856

# Convert it to binary
nbin = n.digits(2)
print "The binary version of n (in reverse order) is", nbin
print "Which has a length of ", len(nbin)

The binary version of n (in reverse order) is [0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1] Which has a length of 106

# Compute the exponents of x up to x^n using the Fast Exponentiation Algorithm
# The maximum number of computations will be 2*(len(nbin)-1)

for i in range(len(nbin)-1):
    prod = prod * prod; 
    if nbin[len(nbin)-i-2] == 1: 
        prod = prod * x
    print "After the ", len(nbin)-i-2," bit , the exponent is : ", prod

After the 104 bit , the exponent is : x^2 After the 103 bit , the exponent is : x^4 After the 102 bit , the exponent is : x^8 After the 101 bit , the exponent is : x^17 After the 100 bit , the exponent is : x^35 After the 99 bit , the exponent is : x^71 After the 98 bit , the exponent is : x^142 After the 97 bit , the exponent is : x^285 After the 96 bit , the exponent is : x^570 After the 95 bit , the exponent is : x^1141 After the 94 bit , the exponent is : x^2283 After the 93 bit , the exponent is : x^4567 After the 92 bit , the exponent is : x^9135 After the 91 bit , the exponent is : x^18271 After the 90 bit , the exponent is : x^36542 After the 89 bit , the exponent is : x^73085 After the 88 bit , the exponent is : x^146170 After the 87 bit , the exponent is : x^292341 After the 86 bit , the exponent is : x^584682 After the 85 bit , the exponent is : x^1169364 After the 84 bit , the exponent is : x^2338728 After the 83 bit , the exponent is : x^4677456 After the 82 bit , the exponent is : x^9354912 After the 81 bit , the exponent is : x^18709824 After the 80 bit , the exponent is : x^37419649 After the 79 bit , the exponent is : x^74839298 After the 78 bit , the exponent is : x^149678597 After the 77 bit , the exponent is : x^299357195 After the 76 bit , the exponent is : x^598714390 After the 75 bit , the exponent is : x^1197428781 After the 74 bit , the exponent is : x^2394857563 After the 73 bit , the exponent is : x^4789715127 After the 72 bit , the exponent is : x^9579430254 After the 71 bit , the exponent is : x^19158860509 After the 70 bit , the exponent is : x^38317721019 After the 69 bit , the exponent is : x^76635442038 After the 68 bit , the exponent is : x^153270884076 After the 67 bit , the exponent is : x^306541768153 After the 66 bit , the exponent is : x^613083536306 After the 65 bit , the exponent is : x^1226167072612 After the 64 bit , the exponent is : x^2452334145225 After the 63 bit , the exponent is : x^4904668290450 After the 62 bit , the exponent is : x^9809336580900 After the 61 bit , the exponent is : x^19618673161800 After the 60 bit , the exponent is : x^39237346323600 After the 59 bit , the exponent is : x^78474692647200 After the 58 bit , the exponent is : x^156949385294400 After the 57 bit , the exponent is : x^313898770588801 After the 56 bit , the exponent is : x^627797541177602 After the 55 bit , the exponent is : x^1255595082355204 After the 54 bit , the exponent is : x^2511190164710409 After the 53 bit , the exponent is : x^5022380329420818 After the 52 bit , the exponent is : x^10044760658841637 After the 51 bit , the exponent is : x^20089521317683275 After the 50 bit , the exponent is : x^40179042635366551 After the 49 bit , the exponent is : x^80358085270733103 After the 48 bit , the exponent is : x^160716170541466207 After the 47 bit , the exponent is : x^321432341082932415 After the 46 bit , the exponent is : x^642864682165864831 After the 45 bit , the exponent is : x^1285729364331729662 After the 44 bit , the exponent is : x^2571458728663459325 After the 43 bit , the exponent is : x^5142917457326918651 After the 42 bit , the exponent is : x^10285834914653837303L After the 41 bit , the exponent is : x^20571669829307674606L After the 40 bit , the exponent is : x^41143339658615349213L After the 39 bit , the exponent is : x^82286679317230698427L After the 38 bit , the exponent is : x^164573358634461396854L After the 37 bit , the exponent is : x^329146717268922793708L After the 36 bit , the exponent is : x^658293434537845587417L After the 35 bit , the exponent is : x^1316586869075691174834L After the 34 bit , the exponent is : x^2633173738151382349669L After the 33 bit , the exponent is : x^5266347476302764699338L After the 32 bit , the exponent is : x^10532694952605529398676L After the 31 bit , the exponent is : x^21065389905211058797352L After the 30 bit , the exponent is : x^42130779810422117594705L After the 29 bit , the exponent is : x^84261559620844235189411L After the 28 bit , the exponent is : x^168523119241688470378822L After the 27 bit , the exponent is : x^337046238483376940757645L After the 26 bit , the exponent is : x^674092476966753881515290L After the 25 bit , the exponent is : x^1348184953933507763030581L After the 24 bit , the exponent is : x^2696369907867015526061162L After the 23 bit , the exponent is : x^5392739815734031052122325L After the 22 bit , the exponent is : x^10785479631468062104244650L After the 21 bit , the exponent is : x^21570959262936124208489301L After the 20 bit , the exponent is : x^43141918525872248416978603L After the 19 bit , the exponent is : x^86283837051744496833957206L After the 18 bit , the exponent is : x^172567674103488993667914413L After the 17 bit , the exponent is : x^345135348206977987335828827L After the 16 bit , the exponent is : x^690270696413955974671657654L After the 15 bit , the exponent is : x^1380541392827911949343315308L After the 14 bit , the exponent is : x^2761082785655823898686630616L After the 13 bit , the exponent is : x^5522165571311647797373261232L After the 12 bit , the exponent is : x^11044331142623295594746522464L After the 11 bit , the exponent is : x^22088662285246591189493044928L After the 10 bit , the exponent is : x^44177324570493182378986089857L After the 9 bit , the exponent is : x^88354649140986364757972179714L After the 8 bit , the exponent is : x^176709298281972729515944359429L After the 7 bit , the exponent is : x^353418596563945459031888718858L After the 6 bit , the exponent is : x^706837193127890918063777437716L After the 5 bit , the exponent is : x^1413674386255781836127554875433L After the 4 bit , the exponent is : x^2827348772511563672255109750866L After the 3 bit , the exponent is : x^5654697545023127344510219501732L After the 2 bit , the exponent is : x^11309395090046254689020439003464L After the 1 bit , the exponent is : x^22618790180092509378040878006928L After the 0 bit , the exponent is : x^45237580360185018756081756013856L