/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / a_utils / perl / mac-perl / mcprl401.bin / Perl_appl / lib / bigint.pl

< prev

next >

MacOS 8.1

Win98

DOS

browse contents

view JSON data

view as text

+--------+-------------------------+-------------------------+--------+--------+
|00000000| 00 09 62 69 67 69 6e 74 | 2e 70 6c 00 00 00 00 00 |..bigint|.pl.....|
|00000010| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000020| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000030| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000040| 00 54 45 58 54 4d 50 53 | 20 00 00 00 00 00 00 00 |.TEXTMPS| .......|
|00000050| 00 00 00 00 00 1d 95 00 | 00 01 ac a6 eb de 36 a6 |........|......6.|
|00000060| eb de 36 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |..6.....|........|
|00000070| 00 00 00 00 00 00 00 00 | 00 00 81 81 48 5f 00 00 |........|....H_..|
|00000080| 70 61 63 6b 61 67 65 20 | 62 69 67 69 6e 74 3b 0d |package |bigint;.|
|00000090| 0d 23 20 61 72 62 69 74 | 72 61 72 79 20 73 69 7a |.# arbit|rary siz|
|000000a0| 65 20 69 6e 74 65 67 65 | 72 20 6d 61 74 68 20 70 |e intege|r math p|
|000000b0| 61 63 6b 61 67 65 0d 23 | 0d 23 20 62 79 20 4d 61 |ackage.#|.# by Ma|
|000000c0| 72 6b 20 42 69 67 67 61 | 72 0d 23 0d 23 20 43 61 |rk Bigga|r.#.# Ca|
|000000d0| 6e 6f 6e 69 63 61 6c 20 | 42 69 67 20 69 6e 74 65 |nonical |Big inte|
|000000e0| 67 65 72 20 76 61 6c 75 | 65 20 61 72 65 20 73 74 |ger valu|e are st|
|000000f0| 72 69 6e 67 73 20 6f 66 | 20 74 68 65 20 66 6f 72 |rings of| the for|
|00000100| 6d 0d 23 20 20 20 20 20 | 20 20 2f 5e 5b 2b 2d 5d |m.#     |  /^[+-]|
|00000110| 5c 64 2b 24 2f 20 77 69 | 74 68 20 6c 65 61 64 69 |\d+$/ wi|th leadi|
|00000120| 6e 67 20 7a 65 72 6f 73 | 20 73 75 70 70 72 65 73 |ng zeros| suppres|
|00000130| 73 65 64 0d 23 20 49 6e | 70 75 74 20 76 61 6c 75 |sed.# In|put valu|
|00000140| 65 73 20 74 6f 20 74 68 | 65 73 65 20 72 6f 75 74 |es to th|ese rout|
|00000150| 69 6e 65 73 20 6d 61 79 | 20 62 65 20 73 74 72 69 |ines may| be stri|
|00000160| 6e 67 73 20 6f 66 20 74 | 68 65 20 66 6f 72 6d 0d |ngs of t|he form.|
|00000170| 23 20 20 20 20 20 20 20 | 2f 5e 5c 73 2a 5b 2b 2d |#       |/^\s*[+-|
|00000180| 5d 3f 5b 5c 64 5c 73 5d | 2b 24 2f 2e 0d 23 20 45 |]?[\d\s]|+$/..# E|
|00000190| 78 61 6d 70 6c 65 73 3a | 0d 23 20 20 20 27 2b 30 |xamples:|.#   '+0|
|000001a0| 27 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |'       |        |
|000001b0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 63 61 6e |        |     can|
|000001c0| 6f 6e 69 63 61 6c 20 7a | 65 72 6f 20 76 61 6c 75 |onical z|ero valu|
|000001d0| 65 0d 23 20 20 20 27 20 | 20 20 2d 31 32 33 20 31 |e.#   ' |  -123 1|
|000001e0| 32 33 20 31 32 33 27 20 | 20 20 20 20 20 20 20 20 |23 123' |        |
|000001f0| 20 20 20 20 20 20 63 61 | 6e 6f 6e 69 63 61 6c 20 |      ca|nonical |
|00000200| 76 61 6c 75 65 20 27 2d | 31 32 33 31 32 33 31 32 |value '-|12312312|
|00000210| 33 27 0d 23 20 20 20 27 | 31 20 32 33 20 34 35 36 |3'.#   '|1 23 456|
|00000220| 20 37 38 39 30 27 20 20 | 20 20 20 20 20 20 20 20 | 7890'  |        |
|00000230| 20 20 20 20 20 20 20 63 | 61 6e 6f 6e 69 63 61 6c |       c|anonical|
|00000240| 20 76 61 6c 75 65 20 27 | 2b 31 32 33 34 35 36 37 | value '|+1234567|
|00000250| 38 39 30 27 0d 23 20 4f | 75 74 70 75 74 20 76 61 |890'.# O|utput va|
|00000260| 6c 75 65 73 20 61 6c 77 | 61 79 73 20 61 6c 77 61 |lues alw|ays alwa|
|00000270| 79 73 20 69 6e 20 63 61 | 6e 6f 6e 69 63 61 6c 20 |ys in ca|nonical |
|00000280| 66 6f 72 6d 0d 23 0d 23 | 20 41 63 74 75 61 6c 20 |form.#.#| Actual |
|00000290| 6d 61 74 68 20 69 73 20 | 64 6f 6e 65 20 69 6e 20 |math is |done in |
|000002a0| 61 6e 20 69 6e 74 65 72 | 6e 61 6c 20 66 6f 72 6d |an inter|nal form|
|000002b0| 61 74 20 63 6f 6e 73 69 | 73 74 69 6e 67 20 6f 66 |at consi|sting of|
|000002c0| 20 61 6e 20 61 72 72 61 | 79 0d 23 20 20 20 77 68 | an arra|y.#   wh|
|000002d0| 6f 73 65 20 66 69 72 73 | 74 20 65 6c 65 6d 65 6e |ose firs|t elemen|
|000002e0| 74 20 69 73 20 74 68 65 | 20 73 69 67 6e 20 28 2f |t is the| sign (/|
|000002f0| 5e 5b 2b 2d 5d 24 2f 29 | 20 61 6e 64 20 77 68 6f |^[+-]$/)| and who|
|00000300| 73 65 20 72 65 6d 61 69 | 6e 69 6e 67 20 0d 23 20 |se remai|ning .# |
|00000310| 20 20 65 6c 65 6d 65 6e | 74 73 20 61 72 65 20 62 |  elemen|ts are b|
|00000320| 61 73 65 20 31 30 30 30 | 30 30 20 64 69 67 69 74 |ase 1000|00 digit|
|00000330| 73 20 77 69 74 68 20 74 | 68 65 20 6c 65 61 73 74 |s with t|he least|
|00000340| 20 73 69 67 6e 69 66 69 | 63 61 6e 74 20 64 69 67 | signifi|cant dig|
|00000350| 69 74 20 66 69 72 73 74 | 2e 0d 23 20 54 68 65 20 |it first|..# The |
|00000360| 73 74 72 69 6e 67 20 27 | 4e 61 4e 27 20 69 73 20 |string '|NaN' is |
|00000370| 75 73 65 64 20 74 6f 20 | 72 65 70 72 65 73 65 6e |used to |represen|
|00000380| 74 20 74 68 65 20 72 65 | 73 75 6c 74 20 77 68 65 |t the re|sult whe|
|00000390| 6e 20 69 6e 70 75 74 20 | 61 72 67 75 6d 65 6e 74 |n input |argument|
|000003a0| 73 20 0d 23 20 20 20 61 | 72 65 20 6e 6f 74 20 6e |s .#   a|re not n|
|000003b0| 75 6d 62 65 72 73 2c 20 | 61 73 20 77 65 6c 6c 20 |umbers, |as well |
|000003c0| 61 73 20 74 68 65 20 72 | 65 73 75 6c 74 20 6f 66 |as the r|esult of|
|000003d0| 20 64 69 76 69 64 69 6e | 67 20 62 79 20 7a 65 72 | dividin|g by zer|
|000003e0| 6f 0d 23 0d 23 20 72 6f | 75 74 69 6e 65 73 20 70 |o.#.# ro|utines p|
|000003f0| 72 6f 76 69 64 65 64 20 | 61 72 65 3a 0d 23 0d 23 |rovided |are:.#.#|
|00000400| 20 20 20 62 6e 65 67 28 | 42 49 4e 54 29 20 72 65 |   bneg(|BINT) re|
|00000410| 74 75 72 6e 20 42 49 4e | 54 20 20 20 20 20 20 20 |turn BIN|T       |
|00000420| 20 20 20 20 20 20 20 6e | 65 67 61 74 69 6f 6e 0d |       n|egation.|
|00000430| 23 20 20 20 62 61 62 73 | 28 42 49 4e 54 29 20 72 |#   babs|(BINT) r|
|00000440| 65 74 75 72 6e 20 42 49 | 4e 54 20 20 20 20 20 20 |eturn BI|NT      |
|00000450| 20 20 20 20 20 20 20 20 | 61 62 73 6f 6c 75 74 65 |        |absolute|
|00000460| 20 76 61 6c 75 65 0d 23 | 20 20 20 62 63 6d 70 28 | value.#|   bcmp(|
|00000470| 42 49 4e 54 2c 42 49 4e | 54 29 20 72 65 74 75 72 |BINT,BIN|T) retur|
|00000480| 6e 20 43 4f 44 45 20 20 | 20 20 20 20 20 20 20 63 |n CODE  |       c|
|00000490| 6f 6d 70 61 72 65 20 6e | 75 6d 62 65 72 73 20 28 |ompare n|umbers (|
|000004a0| 75 6e 64 65 66 2c 3c 30 | 2c 3d 30 2c 3e 30 29 0d |undef,<0|,=0,>0).|
|000004b0| 23 20 20 20 62 61 64 64 | 28 42 49 4e 54 2c 42 49 |#   badd|(BINT,BI|
|000004c0| 4e 54 29 20 72 65 74 75 | 72 6e 20 42 49 4e 54 20 |NT) retu|rn BINT |
|000004d0| 20 20 20 20 20 20 20 20 | 61 64 64 69 74 69 6f 6e |        |addition|
|000004e0| 0d 23 20 20 20 62 73 75 | 62 28 42 49 4e 54 2c 42 |.#   bsu|b(BINT,B|
|000004f0| 49 4e 54 29 20 72 65 74 | 75 72 6e 20 42 49 4e 54 |INT) ret|urn BINT|
|00000500| 20 20 20 20 20 20 20 20 | 20 73 75 62 74 72 61 63 |        | subtrac|
|00000510| 74 69 6f 6e 0d 23 20 20 | 20 62 6d 75 6c 28 42 49 |tion.#  | bmul(BI|
|00000520| 4e 54 2c 42 49 4e 54 29 | 20 72 65 74 75 72 6e 20 |NT,BINT)| return |
|00000530| 42 49 4e 54 20 20 20 20 | 20 20 20 20 20 6d 75 6c |BINT    |     mul|
|00000540| 74 69 70 6c 69 63 61 74 | 69 6f 6e 0d 23 20 20 20 |tiplicat|ion.#   |
|00000550| 62 64 69 76 28 42 49 4e | 54 2c 42 49 4e 54 29 20 |bdiv(BIN|T,BINT) |
|00000560| 72 65 74 75 72 6e 20 28 | 42 49 4e 54 2c 42 49 4e |return (|BINT,BIN|
|00000570| 54 29 20 20 64 69 76 69 | 73 69 6f 6e 20 28 71 75 |T)  divi|sion (qu|
|00000580| 6f 2c 72 65 6d 29 20 6a | 75 73 74 20 71 75 6f 20 |o,rem) j|ust quo |
|00000590| 69 66 20 73 63 61 6c 61 | 72 0d 23 20 20 20 62 6d |if scala|r.#   bm|
|000005a0| 6f 64 28 42 49 4e 54 2c | 42 49 4e 54 29 20 72 65 |od(BINT,|BINT) re|
|000005b0| 74 75 72 6e 20 42 49 4e | 54 20 20 20 20 20 20 20 |turn BIN|T       |
|000005c0| 20 20 6d 6f 64 75 6c 75 | 73 0d 23 20 20 20 62 67 |  modulu|s.#   bg|
|000005d0| 63 64 28 42 49 4e 54 2c | 42 49 4e 54 29 20 72 65 |cd(BINT,|BINT) re|
|000005e0| 74 75 72 6e 20 42 49 4e | 54 20 20 20 20 20 20 20 |turn BIN|T       |
|000005f0| 20 20 67 72 65 61 74 65 | 73 74 20 63 6f 6d 6d 6f |  greate|st commo|
|00000600| 6e 20 64 69 76 69 73 6f | 72 0d 23 20 20 20 62 6e |n diviso|r.#   bn|
|00000610| 6f 72 6d 28 42 49 4e 54 | 29 20 72 65 74 75 72 6e |orm(BINT|) return|
|00000620| 20 42 49 4e 54 20 20 20 | 20 20 20 20 20 20 20 20 | BINT   |        |
|00000630| 20 20 6e 6f 72 6d 61 6c | 69 7a 61 74 69 6f 6e 0d |  normal|ization.|
|00000640| 23 0d 0c 0d 23 20 6e 6f | 72 6d 61 6c 69 7a 65 20 |#...# no|rmalize |
|00000650| 73 74 72 69 6e 67 20 66 | 6f 72 6d 20 6f 66 20 6e |string f|orm of n|
|00000660| 75 6d 62 65 72 2e 20 20 | 20 53 74 72 69 70 20 6c |umber.  | Strip l|
|00000670| 65 61 64 69 6e 67 20 7a | 65 72 6f 73 2e 20 20 53 |eading z|eros.  S|
|00000680| 74 72 69 70 20 61 6e 79 | 0d 23 20 20 20 77 68 69 |trip any|.#   whi|
|00000690| 74 65 20 73 70 61 63 65 | 20 61 6e 64 20 61 64 64 |te space| and add|
|000006a0| 20 61 20 73 69 67 6e 2c | 20 69 66 20 6d 69 73 73 | a sign,| if miss|
|000006b0| 69 6e 67 2e 0d 23 20 53 | 74 72 69 6e 67 73 20 74 |ing..# S|trings t|
|000006c0| 68 61 74 20 61 72 65 20 | 6e 6f 74 20 6e 75 6d 62 |hat are |not numb|
|000006d0| 65 72 73 20 72 65 73 75 | 6c 74 20 74 68 65 20 76 |ers resu|lt the v|
|000006e0| 61 6c 75 65 20 27 4e 61 | 4e 27 2e 0d 73 75 62 20 |alue 'Na|N'..sub |
|000006f0| 6d 61 69 6e 27 62 6e 6f | 72 6d 20 7b 20 23 28 6e |main'bno|rm { #(n|
|00000700| 75 6d 5f 73 74 72 29 20 | 72 65 74 75 72 6e 20 6e |um_str) |return n|
|00000710| 75 6d 5f 73 74 72 0d 20 | 20 20 20 6c 6f 63 61 6c |um_str. |   local|
|00000720| 28 24 5f 29 20 3d 20 40 | 5f 3b 0d 20 20 20 20 73 |($_) = @|_;.    s|
|00000730| 2f 5c 73 2b 2f 2f 67 3b | 20 20 20 20 20 20 20 20 |/\s+//g;|        |
|00000740| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00000750| 20 20 20 23 20 73 74 72 | 69 70 20 77 68 69 74 65 |   # str|ip white|
|00000760| 20 73 70 61 63 65 0d 20 | 20 20 20 69 66 20 28 73 | space. |   if (s|
|00000770| 2f 5e 28 5b 2b 2d 5d 3f | 29 30 2a 28 5c 64 2b 29 |/^([+-]?|)0*(\d+)|
|00000780| 24 2f 24 31 24 32 2f 29 | 20 7b 20 20 20 20 20 23 |$/$1$2/)| {     #|
|00000790| 20 74 65 73 74 20 69 66 | 20 6e 75 6d 62 65 72 0d | test if| number.|
|000007a0| 09 73 75 62 73 74 72 28 | 24 5f 2c 30 2c 30 29 20 |.substr(|$_,0,0) |
|000007b0| 3d 20 27 2b 27 20 75 6e | 6c 65 73 73 20 24 31 3b |= '+' un|less $1;|
|000007c0| 20 23 20 41 64 64 20 6d | 69 73 73 69 6e 67 20 73 | # Add m|issing s|
|000007d0| 69 67 6e 0d 09 73 2f 5e | 2d 30 2f 2b 30 2f 3b 0d |ign..s/^|-0/+0/;.|
|000007e0| 09 24 5f 3b 0d 20 20 20 | 20 7d 20 65 6c 73 65 20 |.$_;.   | } else |
|000007f0| 7b 0d 09 27 4e 61 4e 27 | 3b 0d 20 20 20 20 7d 0d |{..'NaN'|;.    }.|
|00000800| 7d 0d 0d 23 20 43 6f 6e | 76 65 72 74 20 61 20 6e |}..# Con|vert a n|
|00000810| 75 6d 62 65 72 20 66 72 | 6f 6d 20 73 74 72 69 6e |umber fr|om strin|
|00000820| 67 20 66 6f 72 6d 61 74 | 20 74 6f 20 69 6e 74 65 |g format| to inte|
|00000830| 72 6e 61 6c 20 62 61 73 | 65 20 31 30 30 30 30 30 |rnal bas|e 100000|
|00000840| 20 66 6f 72 6d 61 74 2e | 0d 23 20 20 20 41 73 73 | format.|.#   Ass|
|00000850| 75 6d 65 73 20 6e 6f 72 | 6d 61 6c 69 7a 65 64 20 |umes nor|malized |
|00000860| 76 61 6c 75 65 20 61 73 | 20 69 6e 70 75 74 2e 0d |value as| input..|
|00000870| 73 75 62 20 69 6e 74 65 | 72 6e 61 6c 20 7b 20 23 |sub inte|rnal { #|
|00000880| 28 6e 75 6d 5f 73 74 72 | 29 20 72 65 74 75 72 6e |(num_str|) return|
|00000890| 20 69 6e 74 5f 6e 75 6d | 5f 61 72 72 61 79 0d 20 | int_num|_array. |
|000008a0| 20 20 20 6c 6f 63 61 6c | 28 24 64 29 20 3d 20 40 |   local|($d) = @|
|000008b0| 5f 3b 0d 20 20 20 20 28 | 24 69 73 2c 24 69 6c 29 |_;.    (|$is,$il)|
|000008c0| 20 3d 20 28 73 75 62 73 | 74 72 28 24 64 2c 30 2c | = (subs|tr($d,0,|
|000008d0| 31 29 2c 6c 65 6e 67 74 | 68 28 24 64 29 2d 32 29 |1),lengt|h($d)-2)|
|000008e0| 3b 0d 20 20 20 20 73 75 | 62 73 74 72 28 24 64 2c |;.    su|bstr($d,|
|000008f0| 30 2c 31 29 20 3d 20 27 | 27 3b 0d 20 20 20 20 28 |0,1) = '|';.    (|
|00000900| 24 69 73 2c 20 72 65 76 | 65 72 73 65 28 75 6e 70 |$is, rev|erse(unp|
|00000910| 61 63 6b 28 22 61 22 20 | 2e 20 28 24 69 6c 25 35 |ack("a" |. ($il%5|
|00000920| 2b 31 29 20 2e 20 28 22 | 61 35 22 20 78 20 28 24 |+1) . ("|a5" x ($|
|00000930| 69 6c 2f 35 29 29 2c 20 | 24 64 29 29 29 3b 0d 7d |il/5)), |$d)));.}|
|00000940| 0d 0d 23 20 43 6f 6e 76 | 65 72 74 20 61 20 6e 75 |..# Conv|ert a nu|
|00000950| 6d 62 65 72 20 66 72 6f | 6d 20 69 6e 74 65 72 6e |mber fro|m intern|
|00000960| 61 6c 20 62 61 73 65 20 | 31 30 30 30 30 30 20 66 |al base |100000 f|
|00000970| 6f 72 6d 61 74 20 74 6f | 20 73 74 72 69 6e 67 20 |ormat to| string |
|00000980| 66 6f 72 6d 61 74 2e 0d | 23 20 20 20 54 68 69 73 |format..|#   This|
|00000990| 20 72 6f 75 74 69 6e 65 | 20 73 63 72 69 62 62 6c | routine| scribbl|
|000009a0| 65 73 20 61 6c 6c 20 6f | 76 65 72 20 69 6e 70 75 |es all o|ver inpu|
|000009b0| 74 20 61 72 72 61 79 2e | 0d 73 75 62 20 65 78 74 |t array.|.sub ext|
|000009c0| 65 72 6e 61 6c 20 7b 20 | 23 28 69 6e 74 5f 6e 75 |ernal { |#(int_nu|
|000009d0| 6d 5f 61 72 72 61 79 29 | 20 72 65 74 75 72 6e 20 |m_array)| return |
|000009e0| 6e 75 6d 5f 73 74 72 0d | 20 20 20 20 24 65 73 20 |num_str.|    $es |
|000009f0| 3d 20 73 68 69 66 74 3b | 0d 20 20 20 20 67 72 65 |= shift;|.    gre|
|00000a00| 70 28 24 5f 20 3e 20 39 | 39 39 39 20 7c 7c 20 28 |p($_ > 9|999 || (|
|00000a10| 24 5f 20 3d 20 73 75 62 | 73 74 72 28 27 30 30 30 |$_ = sub|str('000|
|00000a20| 30 27 2e 24 5f 2c 2d 35 | 29 29 2c 20 40 5f 29 3b |0'.$_,-5|)), @_);|
|00000a30| 20 20 20 23 20 7a 65 72 | 6f 20 70 61 64 0d 20 20 |   # zer|o pad.  |
|00000a40| 20 20 26 27 62 6e 6f 72 | 6d 28 6a 6f 69 6e 28 27 |  &'bnor|m(join('|
|00000a50| 27 2c 20 24 65 73 2c 20 | 72 65 76 65 72 73 65 28 |', $es, |reverse(|
|00000a60| 40 5f 29 29 29 3b 20 20 | 20 20 23 20 72 65 76 65 |@_)));  |  # reve|
|00000a70| 72 73 65 20 63 6f 6e 63 | 61 74 20 61 6e 64 20 6e |rse conc|at and n|
|00000a80| 6f 72 6d 61 6c 69 7a 65 | 0d 7d 0d 0d 23 20 4e 65 |ormalize|.}..# Ne|
|00000a90| 67 61 74 65 20 69 6e 70 | 75 74 20 76 61 6c 75 65 |gate inp|ut value|
|00000aa0| 2e 0d 73 75 62 20 6d 61 | 69 6e 27 62 6e 65 67 20 |..sub ma|in'bneg |
|00000ab0| 7b 20 23 28 6e 75 6d 5f | 73 74 72 29 20 72 65 74 |{ #(num_|str) ret|
|00000ac0| 75 72 6e 20 6e 75 6d 5f | 73 74 72 0d 20 20 20 20 |urn num_|str.    |
|00000ad0| 6c 6f 63 61 6c 28 24 5f | 29 20 3d 20 26 27 62 6e |local($_|) = &'bn|
|00000ae0| 6f 72 6d 28 40 5f 29 3b | 0d 20 20 20 20 76 65 63 |orm(@_);|.    vec|
|00000af0| 28 24 5f 2c 30 2c 38 29 | 20 5e 3d 20 6f 72 64 28 |($_,0,8)| ^= ord(|
|00000b00| 27 2b 27 29 20 5e 20 6f | 72 64 28 27 2d 27 29 20 |'+') ^ o|rd('-') |
|00000b10| 75 6e 6c 65 73 73 20 24 | 5f 20 65 71 20 27 2b 30 |unless $|_ eq '+0|
|00000b20| 27 3b 0d 20 20 20 20 73 | 2f 5e 48 2f 4e 2f 3b 0d |';.    s|/^H/N/;.|
|00000b30| 20 20 20 20 24 5f 3b 0d | 7d 0d 0d 23 20 52 65 74 |    $_;.|}..# Ret|
|00000b40| 75 72 6e 73 20 74 68 65 | 20 61 62 73 6f 6c 75 74 |urns the| absolut|
|00000b50| 65 20 76 61 6c 75 65 20 | 6f 66 20 74 68 65 20 69 |e value |of the i|
|00000b60| 6e 70 75 74 2e 0d 73 75 | 62 20 6d 61 69 6e 27 62 |nput..su|b main'b|
|00000b70| 61 62 73 20 7b 20 23 28 | 6e 75 6d 5f 73 74 72 29 |abs { #(|num_str)|
|00000b80| 20 72 65 74 75 72 6e 20 | 6e 75 6d 5f 73 74 72 0d | return |num_str.|
|00000b90| 20 20 20 20 26 61 62 73 | 28 26 27 62 6e 6f 72 6d |    &abs|(&'bnorm|
|00000ba0| 28 40 5f 29 29 3b 0d 7d | 0d 0d 73 75 62 20 61 62 |(@_));.}|..sub ab|
|00000bb0| 73 20 7b 20 23 20 70 6f | 73 74 2d 6e 6f 72 6d 61 |s { # po|st-norma|
|00000bc0| 6c 69 7a 65 64 20 61 62 | 73 20 66 6f 72 20 69 6e |lized ab|s for in|
|00000bd0| 74 65 72 6e 61 6c 20 75 | 73 65 0d 20 20 20 20 6c |ternal u|se.    l|
|00000be0| 6f 63 61 6c 28 24 5f 29 | 20 3d 20 40 5f 3b 0d 20 |ocal($_)| = @_;. |
|00000bf0| 20 20 20 73 2f 5e 2d 2f | 2b 2f 3b 0d 20 20 20 20 |   s/^-/|+/;.    |
|00000c00| 24 5f 3b 0d 7d 0d 0c 0d | 23 20 43 6f 6d 70 61 72 |$_;.}...|# Compar|
|00000c10| 65 73 20 32 20 76 61 6c | 75 65 73 2e 20 20 52 65 |es 2 val|ues.  Re|
|00000c20| 74 75 72 6e 73 20 6f 6e | 65 20 6f 66 20 75 6e 64 |turns on|e of und|
|00000c30| 65 66 2c 20 3c 30 2c 20 | 3d 30 2c 20 3e 30 2e 20 |ef, <0, |=0, >0. |
|00000c40| 28 73 75 69 74 61 62 6c | 65 20 66 6f 72 20 73 6f |(suitabl|e for so|
|00000c50| 72 74 29 0d 73 75 62 20 | 6d 61 69 6e 27 62 63 6d |rt).sub |main'bcm|
|00000c60| 70 20 7b 20 23 28 6e 75 | 6d 5f 73 74 72 2c 20 6e |p { #(nu|m_str, n|
|00000c70| 75 6d 5f 73 74 72 29 20 | 72 65 74 75 72 6e 20 63 |um_str) |return c|
|00000c80| 6f 6e 64 5f 63 6f 64 65 | 0d 20 20 20 20 6c 6f 63 |ond_code|.    loc|
|00000c90| 61 6c 28 24 78 2c 24 79 | 29 20 3d 20 28 26 27 62 |al($x,$y|) = (&'b|
|00000ca0| 6e 6f 72 6d 28 24 5f 5b | 30 5d 29 2c 26 27 62 6e |norm($_[|0]),&'bn|
|00000cb0| 6f 72 6d 28 24 5f 5b 31 | 5d 29 29 3b 0d 20 20 20 |orm($_[1|]));.   |
|00000cc0| 20 69 66 20 28 24 78 20 | 65 71 20 27 4e 61 4e 27 | if ($x |eq 'NaN'|
|00000cd0| 29 20 7b 0d 09 75 6e 64 | 65 66 3b 0d 20 20 20 20 |) {..und|ef;.    |
|00000ce0| 7d 20 65 6c 73 69 66 20 | 28 24 79 20 65 71 20 27 |} elsif |($y eq '|
|00000cf0| 4e 61 4e 27 29 20 7b 0d | 09 75 6e 64 65 66 3b 0d |NaN') {.|.undef;.|
|00000d00| 20 20 20 20 7d 20 65 6c | 73 65 20 7b 0d 09 26 63 |    } el|se {..&c|
|00000d10| 6d 70 28 24 78 2c 24 79 | 29 3b 0d 20 20 20 20 7d |mp($x,$y|);.    }|
|00000d20| 0d 7d 0d 0d 73 75 62 20 | 63 6d 70 20 7b 20 23 20 |.}..sub |cmp { # |
|00000d30| 70 6f 73 74 2d 6e 6f 72 | 6d 61 6c 69 7a 65 64 20 |post-nor|malized |
|00000d40| 63 6f 6d 70 61 72 65 20 | 66 6f 72 20 69 6e 74 65 |compare |for inte|
|00000d50| 72 6e 61 6c 20 75 73 65 | 0d 20 20 20 20 6c 6f 63 |rnal use|.    loc|
|00000d60| 61 6c 28 24 63 78 2c 20 | 24 63 79 29 20 3d 20 40 |al($cx, |$cy) = @|
|00000d70| 5f 3b 0d 20 20 20 20 24 | 63 78 20 63 6d 70 20 24 |_;.    $|cx cmp $|
|00000d80| 63 79 0d 20 20 20 20 26 | 26 0d 20 20 20 20 28 0d |cy.    &|&.    (.|
|00000d90| 09 6f 72 64 28 24 63 79 | 29 20 3c 3d 3e 20 6f 72 |.ord($cy|) <=> or|
|00000da0| 64 28 24 63 78 29 0d 09 | 7c 7c 0d 09 28 24 63 78 |d($cx)..|||..($cx|
|00000db0| 20 63 6d 70 20 27 2c 27 | 29 20 2a 20 28 6c 65 6e | cmp ','|) * (len|
|00000dc0| 67 74 68 28 24 63 79 29 | 20 3c 3d 3e 20 6c 65 6e |gth($cy)| <=> len|
|00000dd0| 67 74 68 28 24 63 78 29 | 20 7c 7c 20 24 63 79 20 |gth($cx)| || $cy |
|00000de0| 63 6d 70 20 24 63 78 29 | 0d 20 20 20 20 29 3b 0d |cmp $cx)|.    );.|
|00000df0| 7d 0d 0d 73 75 62 20 6d | 61 69 6e 27 62 61 64 64 |}..sub m|ain'badd|
|00000e00| 20 7b 20 23 28 6e 75 6d | 5f 73 74 72 2c 20 6e 75 | { #(num|_str, nu|
|00000e10| 6d 5f 73 74 72 29 20 72 | 65 74 75 72 6e 20 6e 75 |m_str) r|eturn nu|
|00000e20| 6d 5f 73 74 72 0d 20 20 | 20 20 6c 6f 63 61 6c 28 |m_str.  |  local(|
|00000e30| 2a 78 2c 20 2a 79 29 3b | 20 28 24 78 2c 20 24 79 |*x, *y);| ($x, $y|
|00000e40| 29 20 3d 20 28 26 27 62 | 6e 6f 72 6d 28 24 5f 5b |) = (&'b|norm($_[|
|00000e50| 30 5d 29 2c 26 27 62 6e | 6f 72 6d 28 24 5f 5b 31 |0]),&'bn|orm($_[1|
|00000e60| 5d 29 29 3b 0d 20 20 20 | 20 69 66 20 28 24 78 20 |]));.   | if ($x |
|00000e70| 65 71 20 27 4e 61 4e 27 | 29 20 7b 0d 09 27 4e 61 |eq 'NaN'|) {..'Na|
|00000e80| 4e 27 3b 0d 20 20 20 20 | 7d 20 65 6c 73 69 66 20 |N';.    |} elsif |
|00000e90| 28 24 79 20 65 71 20 27 | 4e 61 4e 27 29 20 7b 0d |($y eq '|NaN') {.|
|00000ea0| 09 27 4e 61 4e 27 3b 0d | 20 20 20 20 7d 20 65 6c |.'NaN';.|    } el|
|00000eb0| 73 65 20 7b 0d 09 40 78 | 20 3d 20 26 69 6e 74 65 |se {..@x| = &inte|
|00000ec0| 72 6e 61 6c 28 24 78 29 | 3b 20 20 20 20 20 20 20 |rnal($x)|;       |
|00000ed0| 20 20 20 20 20 20 23 20 | 63 6f 6e 76 65 72 74 20 |      # |convert |
|00000ee0| 74 6f 20 69 6e 74 65 72 | 6e 61 6c 20 66 6f 72 6d |to inter|nal form|
|00000ef0| 0d 09 40 79 20 3d 20 26 | 69 6e 74 65 72 6e 61 6c |..@y = &|internal|
|00000f00| 28 24 79 29 3b 0d 09 6c | 6f 63 61 6c 28 24 73 78 |($y);..l|ocal($sx|
|00000f10| 2c 20 24 73 79 29 20 3d | 20 28 73 68 69 66 74 20 |, $sy) =| (shift |
|00000f20| 40 78 2c 20 73 68 69 66 | 74 20 40 79 29 3b 20 23 |@x, shif|t @y); #|
|00000f30| 20 67 65 74 20 73 69 67 | 6e 73 0d 09 69 66 20 28 | get sig|ns..if (|
|00000f40| 24 73 78 20 65 71 20 24 | 73 79 29 20 7b 0d 09 20 |$sx eq $|sy) {.. |
|00000f50| 20 20 20 26 65 78 74 65 | 72 6e 61 6c 28 24 73 78 |   &exte|rnal($sx|
|00000f60| 2c 20 26 61 64 64 28 2a | 78 2c 20 2a 79 29 29 3b |, &add(*|x, *y));|
|00000f70| 20 23 20 69 66 20 73 61 | 6d 65 20 73 69 67 6e 20 | # if sa|me sign |
|00000f80| 61 64 64 0d 09 7d 20 65 | 6c 73 65 20 7b 0d 09 20 |add..} e|lse {.. |
|00000f90| 20 20 20 28 24 78 2c 20 | 24 79 29 20 3d 20 28 26 |   ($x, |$y) = (&|
|00000fa0| 61 62 73 28 24 78 29 2c | 26 61 62 73 28 24 79 29 |abs($x),|&abs($y)|
|00000fb0| 29 3b 20 23 20 6d 61 6b | 65 20 61 62 73 0d 09 20 |); # mak|e abs.. |
|00000fc0| 20 20 20 69 66 20 28 26 | 63 6d 70 28 24 79 2c 24 |   if (&|cmp($y,$|
|00000fd0| 78 29 20 3e 20 30 29 20 | 7b 0d 09 09 26 65 78 74 |x) > 0) |{...&ext|
|00000fe0| 65 72 6e 61 6c 28 24 73 | 79 2c 20 26 73 75 62 28 |ernal($s|y, &sub(|
|00000ff0| 2a 79 2c 20 2a 78 29 29 | 3b 0d 09 20 20 20 20 7d |*y, *x))|;..    }|
|00001000| 20 65 6c 73 65 20 7b 0d | 09 09 26 65 78 74 65 72 | else {.|..&exter|
|00001010| 6e 61 6c 28 24 73 78 2c | 20 26 73 75 62 28 2a 78 |nal($sx,| &sub(*x|
|00001020| 2c 20 2a 79 29 29 3b 0d | 09 20 20 20 20 7d 0d 09 |, *y));.|.    }..|
|00001030| 7d 0d 20 20 20 20 7d 0d | 7d 0d 0d 73 75 62 20 6d |}.    }.|}..sub m|
|00001040| 61 69 6e 27 62 73 75 62 | 20 7b 20 23 28 6e 75 6d |ain'bsub| { #(num|
|00001050| 5f 73 74 72 2c 20 6e 75 | 6d 5f 73 74 72 29 20 72 |_str, nu|m_str) r|
|00001060| 65 74 75 72 6e 20 6e 75 | 6d 5f 73 74 72 0d 20 20 |eturn nu|m_str.  |
|00001070| 20 20 26 27 62 61 64 64 | 28 24 5f 5b 30 5d 2c 26 |  &'badd|($_[0],&|
|00001080| 27 62 6e 65 67 28 24 5f | 5b 31 5d 29 29 3b 20 20 |'bneg($_|[1]));  |
|00001090| 20 20 0d 7d 0d 0d 23 20 | 47 43 44 20 2d 2d 20 45 |  .}..# |GCD -- E|
|000010a0| 75 63 6c 69 64 73 20 61 | 6c 67 6f 72 69 74 68 6d |uclids a|lgorithm|
|000010b0| 20 4b 6e 75 74 68 20 56 | 6f 6c 20 32 20 70 67 20 | Knuth V|ol 2 pg |
|000010c0| 32 39 36 0d 73 75 62 20 | 6d 61 69 6e 27 62 67 63 |296.sub |main'bgc|
|000010d0| 64 20 7b 20 23 28 6e 75 | 6d 5f 73 74 72 2c 20 6e |d { #(nu|m_str, n|
|000010e0| 75 6d 5f 73 74 72 29 20 | 72 65 74 75 72 6e 20 6e |um_str) |return n|
|000010f0| 75 6d 5f 73 74 72 0d 20 | 20 20 20 6c 6f 63 61 6c |um_str. |   local|
|00001100| 28 24 78 2c 24 79 29 20 | 3d 20 28 26 27 62 6e 6f |($x,$y) |= (&'bno|
|00001110| 72 6d 28 24 5f 5b 30 5d | 29 2c 26 27 62 6e 6f 72 |rm($_[0]|),&'bnor|
|00001120| 6d 28 24 5f 5b 31 5d 29 | 29 3b 0d 20 20 20 20 69 |m($_[1])|);.    i|
|00001130| 66 20 28 24 78 20 65 71 | 20 27 4e 61 4e 27 20 7c |f ($x eq| 'NaN' ||
|00001140| 7c 20 24 79 20 65 71 20 | 27 4e 61 4e 27 29 20 7b || $y eq |'NaN') {|
|00001150| 0d 09 27 4e 61 4e 27 3b | 0d 20 20 20 20 7d 20 65 |..'NaN';|.    } e|
|00001160| 6c 73 65 20 7b 0d 09 28 | 24 78 2c 20 24 79 29 20 |lse {..(|$x, $y) |
|00001170| 3d 20 28 24 79 2c 26 27 | 62 6d 6f 64 28 24 78 2c |= ($y,&'|bmod($x,|
|00001180| 24 79 29 29 20 77 68 69 | 6c 65 20 24 79 20 6e 65 |$y)) whi|le $y ne|
|00001190| 20 27 2b 30 27 3b 0d 09 | 24 78 3b 0d 20 20 20 20 | '+0';..|$x;.    |
|000011a0| 7d 0d 7d 0d 0c 0d 23 20 | 72 6f 75 74 69 6e 65 20 |}.}...# |routine |
|000011b0| 74 6f 20 61 64 64 20 74 | 77 6f 20 62 61 73 65 20 |to add t|wo base |
|000011c0| 31 65 35 20 6e 75 6d 62 | 65 72 73 0d 23 20 20 20 |1e5 numb|ers.#   |
|000011d0| 73 74 6f 6c 65 6e 20 66 | 72 6f 6d 20 4b 6e 75 74 |stolen f|rom Knut|
|000011e0| 68 20 56 6f 6c 20 32 20 | 41 6c 67 6f 72 69 74 68 |h Vol 2 |Algorith|
|000011f0| 6d 20 41 20 70 67 20 32 | 33 31 0d 23 20 20 20 74 |m A pg 2|31.#   t|
|00001200| 68 65 72 65 20 61 72 65 | 20 73 65 70 61 72 61 74 |here are| separat|
|00001210| 65 20 72 6f 75 74 69 6e | 65 73 20 74 6f 20 61 64 |e routin|es to ad|
|00001220| 64 20 61 6e 64 20 73 75 | 62 20 61 73 20 70 65 72 |d and su|b as per|
|00001230| 20 4b 75 6e 74 68 20 70 | 67 20 32 33 33 0d 73 75 | Kunth p|g 233.su|
|00001240| 62 20 61 64 64 20 7b 20 | 23 28 69 6e 74 5f 6e 75 |b add { |#(int_nu|
|00001250| 6d 5f 61 72 72 61 79 2c | 20 69 6e 74 5f 6e 75 6d |m_array,| int_num|
|00001260| 5f 61 72 72 61 79 29 20 | 72 65 74 75 72 6e 20 69 |_array) |return i|
|00001270| 6e 74 5f 6e 75 6d 5f 61 | 72 72 61 79 0d 20 20 20 |nt_num_a|rray.   |
|00001280| 20 6c 6f 63 61 6c 28 2a | 78 2c 20 2a 79 29 20 3d | local(*|x, *y) =|
|00001290| 20 40 5f 3b 0d 20 20 20 | 20 24 63 61 72 20 3d 20 | @_;.   | $car = |
|000012a0| 30 3b 0d 20 20 20 20 66 | 6f 72 20 24 78 20 28 40 |0;.    f|or $x (@|
|000012b0| 78 29 20 7b 0d 09 6c 61 | 73 74 20 75 6e 6c 65 73 |x) {..la|st unles|
|000012c0| 73 20 40 79 20 7c 7c 20 | 24 63 61 72 3b 0d 09 24 |s @y || |$car;..$|
|000012d0| 78 20 2d 3d 20 31 65 35 | 20 69 66 20 24 63 61 72 |x -= 1e5| if $car|
|000012e0| 20 3d 20 28 28 24 78 20 | 2b 3d 20 73 68 69 66 74 | = (($x |+= shift|
|000012f0| 20 40 79 20 2b 20 24 63 | 61 72 29 20 3e 3d 20 31 | @y + $c|ar) >= 1|
|00001300| 65 35 29 3b 0d 20 20 20 | 20 7d 0d 20 20 20 20 66 |e5);.   | }.    f|
|00001310| 6f 72 20 24 79 20 28 40 | 79 29 20 7b 0d 09 6c 61 |or $y (@|y) {..la|
|00001320| 73 74 20 75 6e 6c 65 73 | 73 20 24 63 61 72 3b 0d |st unles|s $car;.|
|00001330| 09 24 79 20 2d 3d 20 31 | 65 35 20 69 66 20 24 63 |.$y -= 1|e5 if $c|
|00001340| 61 72 20 3d 20 28 28 24 | 79 20 2b 3d 20 24 63 61 |ar = (($|y += $ca|
|00001350| 72 29 20 3e 3d 20 31 65 | 35 29 3b 0d 20 20 20 20 |r) >= 1e|5);.    |
|00001360| 7d 0d 20 20 20 20 28 40 | 78 2c 20 40 79 2c 20 24 |}.    (@|x, @y, $|
|00001370| 63 61 72 29 3b 0d 7d 0d | 0d 23 20 73 75 62 74 72 |car);.}.|.# subtr|
|00001380| 61 63 74 20 62 61 73 65 | 20 31 65 35 20 6e 75 6d |act base| 1e5 num|
|00001390| 62 65 72 73 20 2d 2d 20 | 73 74 6f 6c 65 6e 20 66 |bers -- |stolen f|
|000013a0| 72 6f 6d 20 4b 6e 75 74 | 68 20 56 6f 6c 20 32 20 |rom Knut|h Vol 2 |
|000013b0| 70 67 20 32 33 32 2c 20 | 24 78 20 3e 20 24 79 0d |pg 232, |$x > $y.|
|000013c0| 73 75 62 20 73 75 62 20 | 7b 20 23 28 69 6e 74 5f |sub sub |{ #(int_|
|000013d0| 6e 75 6d 5f 61 72 72 61 | 79 2c 20 69 6e 74 5f 6e |num_arra|y, int_n|
|000013e0| 75 6d 5f 61 72 72 61 79 | 29 20 72 65 74 75 72 6e |um_array|) return|
|000013f0| 20 69 6e 74 5f 6e 75 6d | 5f 61 72 72 61 79 0d 20 | int_num|_array. |
|00001400| 20 20 20 6c 6f 63 61 6c | 28 2a 73 78 2c 20 2a 73 |   local|(*sx, *s|
|00001410| 79 29 20 3d 20 40 5f 3b | 0d 20 20 20 20 24 62 61 |y) = @_;|.    $ba|
|00001420| 72 20 3d 20 30 3b 0d 20 | 20 20 20 66 6f 72 20 24 |r = 0;. |   for $|
|00001430| 73 78 20 28 40 73 78 29 | 20 7b 0d 09 6c 61 73 74 |sx (@sx)| {..last|
|00001440| 20 75 6e 6c 65 73 73 20 | 40 79 20 7c 7c 20 24 62 | unless |@y || $b|
|00001450| 61 72 3b 0d 09 24 73 78 | 20 2b 3d 20 31 65 35 20 |ar;..$sx| += 1e5 |
|00001460| 69 66 20 24 62 61 72 20 | 3d 20 28 28 24 73 78 20 |if $bar |= (($sx |
|00001470| 2d 3d 20 73 68 69 66 74 | 20 40 73 79 20 2b 20 24 |-= shift| @sy + $|
|00001480| 62 61 72 29 20 3c 20 30 | 29 3b 0d 20 20 20 20 7d |bar) < 0|);.    }|
|00001490| 0d 20 20 20 20 40 73 78 | 3b 0d 7d 0d 0d 23 20 6d |.    @sx|;.}..# m|
|000014a0| 75 6c 74 69 70 6c 79 20 | 74 77 6f 20 6e 75 6d 62 |ultiply |two numb|
|000014b0| 65 72 73 20 2d 2d 20 73 | 74 6f 6c 65 6e 20 66 72 |ers -- s|tolen fr|
|000014c0| 6f 6d 20 4b 6e 75 74 68 | 20 56 6f 6c 20 32 20 70 |om Knuth| Vol 2 p|
|000014d0| 67 20 32 33 33 0d 73 75 | 62 20 6d 61 69 6e 27 62 |g 233.su|b main'b|
|000014e0| 6d 75 6c 20 7b 20 23 28 | 6e 75 6d 5f 73 74 72 2c |mul { #(|num_str,|
|000014f0| 20 6e 75 6d 5f 73 74 72 | 29 20 72 65 74 75 72 6e | num_str|) return|
|00001500| 20 6e 75 6d 5f 73 74 72 | 0d 20 20 20 20 6c 6f 63 | num_str|.    loc|
|00001510| 61 6c 28 2a 78 2c 20 2a | 79 29 3b 20 28 24 78 2c |al(*x, *|y); ($x,|
|00001520| 20 24 79 29 20 3d 20 28 | 26 27 62 6e 6f 72 6d 28 | $y) = (|&'bnorm(|
|00001530| 24 5f 5b 30 5d 29 2c 20 | 26 27 62 6e 6f 72 6d 28 |$_[0]), |&'bnorm(|
|00001540| 24 5f 5b 31 5d 29 29 3b | 0d 20 20 20 20 69 66 20 |$_[1]));|.    if |
|00001550| 28 24 78 20 65 71 20 27 | 4e 61 4e 27 29 20 7b 0d |($x eq '|NaN') {.|
|00001560| 09 27 4e 61 4e 27 3b 0d | 20 20 20 20 7d 20 65 6c |.'NaN';.|    } el|
|00001570| 73 69 66 20 28 24 79 20 | 65 71 20 27 4e 61 4e 27 |sif ($y |eq 'NaN'|
|00001580| 29 20 7b 0d 09 27 4e 61 | 4e 27 3b 0d 20 20 20 20 |) {..'Na|N';.    |
|00001590| 7d 20 65 6c 73 65 20 7b | 0d 09 40 78 20 3d 20 26 |} else {|..@x = &|
|000015a0| 69 6e 74 65 72 6e 61 6c | 28 24 78 29 3b 0d 09 40 |internal|($x);..@|
|000015b0| 79 20 3d 20 26 69 6e 74 | 65 72 6e 61 6c 28 24 79 |y = &int|ernal($y|
|000015c0| 29 3b 0d 09 6c 6f 63 61 | 6c 28 24 73 69 67 6e 72 |);..loca|l($signr|
|000015d0| 29 20 3d 20 28 73 68 69 | 66 74 20 40 78 20 6e 65 |) = (shi|ft @x ne|
|000015e0| 20 73 68 69 66 74 20 40 | 79 29 20 3f 20 27 2d 27 | shift @|y) ? '-'|
|000015f0| 20 3a 20 27 2b 27 3b 0d | 09 40 70 72 6f 64 20 3d | : '+';.|.@prod =|
|00001600| 20 28 29 3b 0d 09 66 6f | 72 20 24 78 20 28 40 78 | ();..fo|r $x (@x|
|00001610| 29 20 7b 0d 09 20 20 20 | 20 28 24 63 61 72 2c 20 |) {..   | ($car, |
|00001620| 24 63 74 79 29 20 3d 20 | 28 30 2c 20 30 29 3b 0d |$cty) = |(0, 0);.|
|00001630| 09 20 20 20 20 66 6f 72 | 20 24 79 20 28 40 79 29 |.    for| $y (@y)|
|00001640| 20 7b 0d 09 09 24 70 72 | 6f 64 20 3d 20 24 78 20 | {...$pr|od = $x |
|00001650| 2a 20 24 79 20 2b 20 24 | 70 72 6f 64 5b 24 63 74 |* $y + $|prod[$ct|
|00001660| 79 5d 20 2b 20 24 63 61 | 72 3b 0d 09 09 24 70 72 |y] + $ca|r;...$pr|
|00001670| 6f 64 5b 24 63 74 79 2b | 2b 5d 20 3d 0d 09 09 20 |od[$cty+|+] =... |
|00001680| 20 20 20 24 70 72 6f 64 | 20 2d 20 28 24 63 61 72 |   $prod| - ($car|
|00001690| 20 3d 20 69 6e 74 28 24 | 70 72 6f 64 20 2a 20 31 | = int($|prod * 1|
|000016a0| 65 2d 35 29 29 20 2a 20 | 31 65 35 3b 0d 09 20 20 |e-5)) * |1e5;..  |
|000016b0| 20 20 7d 0d 09 20 20 20 | 20 24 70 72 6f 64 5b 24 |  }..   | $prod[$|
|000016c0| 63 74 79 5d 20 2b 3d 20 | 24 63 61 72 20 69 66 20 |cty] += |$car if |
|000016d0| 24 63 61 72 3b 0d 09 20 | 20 20 20 24 78 20 3d 20 |$car;.. |   $x = |
|000016e0| 73 68 69 66 74 20 40 70 | 72 6f 64 3b 0d 09 7d 0d |shift @p|rod;..}.|
|000016f0| 09 26 65 78 74 65 72 6e | 61 6c 28 24 73 69 67 6e |.&extern|al($sign|
|00001700| 72 2c 20 40 78 2c 20 40 | 70 72 6f 64 29 3b 0d 20 |r, @x, @|prod);. |
|00001710| 20 20 20 7d 0d 7d 0d 0d | 23 20 6d 6f 64 75 6c 75 |   }.}..|# modulu|
|00001720| 73 0d 73 75 62 20 6d 61 | 69 6e 27 62 6d 6f 64 20 |s.sub ma|in'bmod |
|00001730| 7b 20 23 28 6e 75 6d 5f | 73 74 72 2c 20 6e 75 6d |{ #(num_|str, num|
|00001740| 5f 73 74 72 29 20 72 65 | 74 75 72 6e 20 6e 75 6d |_str) re|turn num|
|00001750| 5f 73 74 72 0d 20 20 20 | 20 28 26 27 62 64 69 76 |_str.   | (&'bdiv|
|00001760| 28 40 5f 29 29 5b 31 5d | 3b 0d 7d 0d 0c 0d 73 75 |(@_))[1]|;.}...su|
|00001770| 62 20 6d 61 69 6e 27 62 | 64 69 76 20 7b 20 23 28 |b main'b|div { #(|
|00001780| 64 69 76 69 64 65 6e 64 | 3a 20 6e 75 6d 5f 73 74 |dividend|: num_st|
|00001790| 72 2c 20 64 69 76 69 73 | 6f 72 3a 20 6e 75 6d 5f |r, divis|or: num_|
|000017a0| 73 74 72 29 20 72 65 74 | 75 72 6e 20 6e 75 6d 5f |str) ret|urn num_|
|000017b0| 73 74 72 0d 20 20 20 20 | 6c 6f 63 61 6c 20 28 2a |str.    |local (*|
|000017c0| 78 2c 20 2a 79 29 3b 20 | 28 24 78 2c 20 24 79 29 |x, *y); |($x, $y)|
|000017d0| 20 3d 20 28 26 27 62 6e | 6f 72 6d 28 24 5f 5b 30 | = (&'bn|orm($_[0|
|000017e0| 5d 29 2c 20 26 27 62 6e | 6f 72 6d 28 24 5f 5b 31 |]), &'bn|orm($_[1|
|000017f0| 5d 29 29 3b 0d 20 20 20 | 20 72 65 74 75 72 6e 20 |]));.   | return |
|00001800| 77 61 6e 74 61 72 72 61 | 79 20 3f 20 28 27 4e 61 |wantarra|y ? ('Na|
|00001810| 4e 27 2c 27 4e 61 4e 27 | 29 20 3a 20 27 4e 61 4e |N','NaN'|) : 'NaN|
|00001820| 27 0d 09 69 66 20 28 24 | 78 20 65 71 20 27 4e 61 |'..if ($|x eq 'Na|
|00001830| 4e 27 20 7c 7c 20 24 79 | 20 65 71 20 27 4e 61 4e |N' || $y| eq 'NaN|
|00001840| 27 20 7c 7c 20 24 79 20 | 65 71 20 27 2b 30 27 29 |' || $y |eq '+0')|
|00001850| 3b 0d 20 20 20 20 72 65 | 74 75 72 6e 20 77 61 6e |;.    re|turn wan|
|00001860| 74 61 72 72 61 79 20 3f | 20 28 27 2b 30 27 2c 24 |tarray ?| ('+0',$|
|00001870| 78 29 20 3a 20 27 2b 30 | 27 20 69 66 20 28 26 63 |x) : '+0|' if (&c|
|00001880| 6d 70 28 26 61 62 73 28 | 24 78 29 2c 26 61 62 73 |mp(&abs(|$x),&abs|
|00001890| 28 24 79 29 29 20 3c 20 | 30 29 3b 0d 20 20 20 20 |($y)) < |0);.    |
|000018a0| 40 78 20 3d 20 26 69 6e | 74 65 72 6e 61 6c 28 24 |@x = &in|ternal($|
|000018b0| 78 29 3b 20 40 79 20 3d | 20 26 69 6e 74 65 72 6e |x); @y =| &intern|
|000018c0| 61 6c 28 24 79 29 3b 0d | 20 20 20 20 24 73 72 65 |al($y);.|    $sre|
|000018d0| 6d 20 3d 20 24 79 5b 30 | 5d 3b 0d 20 20 20 20 24 |m = $y[0|];.    $|
|000018e0| 73 72 20 3d 20 28 73 68 | 69 66 74 20 40 78 20 6e |sr = (sh|ift @x n|
|000018f0| 65 20 73 68 69 66 74 20 | 40 79 29 20 3f 20 27 2d |e shift |@y) ? '-|
|00001900| 27 20 3a 20 27 2b 27 3b | 0d 20 20 20 20 24 63 61 |' : '+';|.    $ca|
|00001910| 72 20 3d 20 24 62 61 72 | 20 3d 20 24 70 72 64 20 |r = $bar| = $prd |
|00001920| 3d 20 30 3b 0d 20 20 20 | 20 69 66 20 28 28 24 64 |= 0;.   | if (($d|
|00001930| 64 20 3d 20 69 6e 74 28 | 31 65 35 2f 28 24 79 5b |d = int(|1e5/($y[|
|00001940| 24 23 79 5d 2b 31 29 29 | 29 20 21 3d 20 31 29 20 |$#y]+1))|) != 1) |
|00001950| 7b 0d 09 66 6f 72 20 24 | 78 20 28 40 78 29 20 7b |{..for $|x (@x) {|
|00001960| 0d 09 20 20 20 20 24 78 | 20 3d 20 24 78 20 2a 20 |..    $x| = $x * |
|00001970| 24 64 64 20 2b 20 24 63 | 61 72 3b 0d 09 20 20 20 |$dd + $c|ar;..   |
|00001980| 20 24 78 20 2d 3d 20 28 | 24 63 61 72 20 3d 20 69 | $x -= (|$car = i|
|00001990| 6e 74 28 24 78 20 2a 20 | 31 65 2d 35 29 29 20 2a |nt($x * |1e-5)) *|
|000019a0| 20 31 65 35 3b 0d 09 7d | 0d 09 70 75 73 68 28 40 | 1e5;..}|..push(@|
|000019b0| 78 2c 20 24 63 61 72 29 | 3b 20 24 63 61 72 20 3d |x, $car)|; $car =|
|000019c0| 20 30 3b 0d 09 66 6f 72 | 20 24 79 20 28 40 79 29 | 0;..for| $y (@y)|
|000019d0| 20 7b 0d 09 20 20 20 20 | 24 79 20 3d 20 24 79 20 | {..    |$y = $y |
|000019e0| 2a 20 24 64 64 20 2b 20 | 24 63 61 72 3b 0d 09 20 |* $dd + |$car;.. |
|000019f0| 20 20 20 24 79 20 2d 3d | 20 28 24 63 61 72 20 3d |   $y -=| ($car =|
|00001a00| 20 69 6e 74 28 24 79 20 | 2a 20 31 65 2d 35 29 29 | int($y |* 1e-5))|
|00001a10| 20 2a 20 31 65 35 3b 0d | 09 7d 0d 20 20 20 20 7d | * 1e5;.|.}.    }|
|00001a20| 0d 20 20 20 20 65 6c 73 | 65 20 7b 0d 09 70 75 73 |.    els|e {..pus|
|00001a30| 68 28 40 78 2c 20 30 29 | 3b 0d 20 20 20 20 7d 0d |h(@x, 0)|;.    }.|
|00001a40| 20 20 20 20 40 71 20 3d | 20 28 29 3b 20 28 24 76 |    @q =| (); ($v|
|00001a50| 32 2c 24 76 31 29 20 3d | 20 40 79 5b 24 23 79 2d |2,$v1) =| @y[$#y-|
|00001a60| 31 2c 24 23 79 5d 3b 0d | 20 20 20 20 77 68 69 6c |1,$#y];.|    whil|
|00001a70| 65 20 28 24 23 78 20 3e | 20 24 23 79 29 20 7b 0d |e ($#x >| $#y) {.|
|00001a80| 09 28 24 75 32 2c 24 75 | 31 2c 24 75 30 29 20 3d |.($u2,$u|1,$u0) =|
|00001a90| 20 40 78 5b 28 24 23 78 | 2d 32 29 2e 2e 24 23 78 | @x[($#x|-2)..$#x|
|00001aa0| 5d 3b 0d 09 24 71 20 3d | 20 28 28 24 75 30 20 3d |];..$q =| (($u0 =|
|00001ab0| 3d 20 24 76 31 29 20 3f | 20 39 39 39 39 39 20 3a |= $v1) ?| 99999 :|
|00001ac0| 20 69 6e 74 28 28 24 75 | 30 2a 31 65 35 2b 24 75 | int(($u|0*1e5+$u|
|00001ad0| 31 29 2f 24 76 31 29 29 | 3b 0d 09 2d 2d 24 71 20 |1)/$v1))|;..--$q |
|00001ae0| 77 68 69 6c 65 20 28 24 | 76 32 2a 24 71 20 3e 20 |while ($|v2*$q > |
|00001af0| 28 24 75 30 2a 31 65 35 | 2b 24 75 31 2d 24 71 2a |($u0*1e5|+$u1-$q*|
|00001b00| 24 76 31 29 2a 31 65 35 | 2b 24 75 32 29 3b 0d 09 |$v1)*1e5|+$u2);..|
|00001b10| 69 66 20 28 24 71 29 20 | 7b 0d 09 20 20 20 20 28 |if ($q) |{..    (|
|00001b20| 24 63 61 72 2c 20 24 62 | 61 72 29 20 3d 20 28 30 |$car, $b|ar) = (0|
|00001b30| 2c 30 29 3b 0d 09 20 20 | 20 20 66 6f 72 20 28 24 |,0);..  |  for ($|
|00001b40| 79 20 3d 20 30 2c 20 24 | 78 20 3d 20 24 23 78 2d |y = 0, $|x = $#x-|
|00001b50| 24 23 79 2d 31 3b 20 24 | 79 20 3c 3d 20 24 23 79 |$#y-1; $|y <= $#y|
|00001b60| 3b 20 2b 2b 24 79 2c 2b | 2b 24 78 29 20 7b 0d 09 |; ++$y,+|+$x) {..|
|00001b70| 09 24 70 72 64 20 3d 20 | 24 71 20 2a 20 24 79 5b |.$prd = |$q * $y[|
|00001b80| 24 79 5d 20 2b 20 24 63 | 61 72 3b 0d 09 09 24 70 |$y] + $c|ar;...$p|
|00001b90| 72 64 20 2d 3d 20 28 24 | 63 61 72 20 3d 20 69 6e |rd -= ($|car = in|
|00001ba0| 74 28 24 70 72 64 20 2a | 20 31 65 2d 35 29 29 20 |t($prd *| 1e-5)) |
|00001bb0| 2a 20 31 65 35 3b 0d 09 | 09 24 78 5b 24 78 5d 20 |* 1e5;..|.$x[$x] |
|00001bc0| 2b 3d 20 31 65 35 20 69 | 66 20 28 24 62 61 72 20 |+= 1e5 i|f ($bar |
|00001bd0| 3d 20 28 28 24 78 5b 24 | 78 5d 20 2d 3d 20 24 70 |= (($x[$|x] -= $p|
|00001be0| 72 64 20 2b 20 24 62 61 | 72 29 20 3c 20 30 29 29 |rd + $ba|r) < 0))|
|00001bf0| 3b 0d 09 20 20 20 20 7d | 0d 09 20 20 20 20 69 66 |;..    }|..    if|
|00001c00| 20 28 24 78 5b 24 23 78 | 5d 20 3c 20 24 63 61 72 | ($x[$#x|] < $car|
|00001c10| 20 2b 20 24 62 61 72 29 | 20 7b 0d 09 09 24 63 61 | + $bar)| {...$ca|
|00001c20| 72 20 3d 20 30 3b 20 2d | 2d 24 71 3b 0d 09 09 66 |r = 0; -|-$q;...f|
|00001c30| 6f 72 20 28 24 79 20 3d | 20 30 2c 20 24 78 20 3d |or ($y =| 0, $x =|
|00001c40| 20 24 23 78 2d 24 23 79 | 2d 31 3b 20 24 79 20 3c | $#x-$#y|-1; $y <|
|00001c50| 3d 20 24 23 79 3b 20 2b | 2b 24 79 2c 2b 2b 24 78 |= $#y; +|+$y,++$x|
|00001c60| 29 20 7b 0d 09 09 20 20 | 20 20 24 78 5b 24 78 5d |) {...  |  $x[$x]|
|00001c70| 20 2d 3d 20 31 65 35 0d | 09 09 09 69 66 20 28 24 | -= 1e5.|...if ($|
|00001c80| 63 61 72 20 3d 20 28 28 | 24 78 5b 24 78 5d 20 2b |car = ((|$x[$x] +|
|00001c90| 3d 20 24 79 5b 24 79 5d | 20 2b 20 24 63 61 72 29 |= $y[$y]| + $car)|
|00001ca0| 20 3e 20 31 65 35 29 29 | 3b 0d 09 09 7d 0d 09 20 | > 1e5))|;...}.. |
|00001cb0| 20 20 20 7d 20 20 20 0d | 09 7d 0d 09 70 6f 70 28 |   }   .|.}..pop(|
|00001cc0| 40 78 29 3b 20 75 6e 73 | 68 69 66 74 28 40 71 2c |@x); uns|hift(@q,|
|00001cd0| 20 24 71 29 3b 0d 20 20 | 20 20 7d 0d 20 20 20 20 | $q);.  |  }.    |
|00001ce0| 69 66 20 28 77 61 6e 74 | 61 72 72 61 79 29 20 7b |if (want|array) {|
|00001cf0| 0d 09 40 64 20 3d 20 28 | 29 3b 0d 09 69 66 20 28 |..@d = (|);..if (|
|00001d00| 24 64 64 20 21 3d 20 31 | 29 20 7b 0d 09 20 20 20 |$dd != 1|) {..   |
|00001d10| 20 24 63 61 72 20 3d 20 | 30 3b 0d 09 20 20 20 20 | $car = |0;..    |
|00001d20| 66 6f 72 20 24 78 20 28 | 72 65 76 65 72 73 65 20 |for $x (|reverse |
|00001d30| 40 78 29 20 7b 0d 09 09 | 24 70 72 64 20 3d 20 24 |@x) {...|$prd = $|
|00001d40| 63 61 72 20 2a 20 31 65 | 35 20 2b 20 24 78 3b 0d |car * 1e|5 + $x;.|
|00001d50| 09 09 24 63 61 72 20 3d | 20 24 70 72 64 20 2d 20 |..$car =| $prd - |
|00001d60| 28 24 74 6d 70 20 3d 20 | 69 6e 74 28 24 70 72 64 |($tmp = |int($prd|
|00001d70| 20 2f 20 24 64 64 29 29 | 20 2a 20 24 64 64 3b 0d | / $dd))| * $dd;.|
|00001d80| 09 09 75 6e 73 68 69 66 | 74 28 40 64 2c 20 24 74 |..unshif|t(@d, $t|
|00001d90| 6d 70 29 3b 0d 09 20 20 | 20 20 7d 0d 09 7d 0d 09 |mp);..  |  }..}..|
|00001da0| 65 6c 73 65 20 7b 0d 09 | 20 20 20 20 40 64 20 3d |else {..|    @d =|
|00001db0| 20 40 78 3b 0d 09 7d 0d | 09 28 26 65 78 74 65 72 | @x;..}.|.(&exter|
|00001dc0| 6e 61 6c 28 24 73 72 2c | 20 40 71 29 2c 20 26 65 |nal($sr,| @q), &e|
|00001dd0| 78 74 65 72 6e 61 6c 28 | 24 73 72 65 6d 2c 20 40 |xternal(|$srem, @|
|00001de0| 64 2c 20 30 29 29 3b 0d | 20 20 20 20 7d 20 65 6c |d, 0));.|    } el|
|00001df0| 73 65 20 7b 0d 09 26 65 | 78 74 65 72 6e 61 6c 28 |se {..&e|xternal(|
|00001e00| 24 73 72 2c 20 40 71 29 | 3b 0d 20 20 20 20 7d 0d |$sr, @q)|;.    }.|
|00001e10| 7d 0d 31 3b 0d 00 00 00 | 00 00 00 00 00 00 00 00 |}.1;....|........|
|00001e20| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00001e30| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00001e40| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00001e50| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00001e60| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00001e70| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00001e80| 00 00 01 00 00 00 01 6e | 00 00 00 6e 00 00 00 3e |.......n|...n...>|
|00001e90| 2a 46 49 4c 45 48 41 4e | 44 4c 45 2c 24 6b 65 79 |*FILEHAN|DLE,$key|
|00001ea0| 2c 24 64 69 63 74 2c 24 | 66 6f 6c 64 29 0d 0d 3b |,$dict,$|fold)..;|
|00001eb0| 09 62 69 67 69 6e 74 2e | 70 6c 02 00 00 00 54 45 |.bigint.|pl....TE|
|00001ec0| 58 54 4d 50 53 20 00 00 | 00 00 00 00 00 00 00 00 |XTMPS ..|........|
|00001ed0| 00 00 54 45 58 54 4d 50 | 53 20 00 00 00 00 00 00 |..TEXTMP|S ......|
|00001ee0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00001ef0| 00 00 a6 ea b0 3e 00 00 | 1d 95 00 00 01 ac 73 74 |.....>..|......st|
|00001f00| 72 69 6e 67 77 69 73 65 | 29 20 74 6f 20 24 6b 65 |ringwise|) to $ke|
|00001f10| 79 2e 20 20 50 61 73 73 | 20 66 6c 61 67 73 20 66 |y.  Pass| flags f|
|00001f20| 6f 72 20 64 69 63 74 69 | 6f 6e 61 72 79 20 6f 72 |or dicti|onary or|
|00001f30| 64 65 72 20 61 6e 64 20 | 63 61 73 65 20 66 6f 6c |der and |case fol|
|00001f40| 64 69 6e 67 2e 0d 0d 73 | 75 62 20 6c 6f 6f 6b 20 |ding...s|ub look |
|00001f50| 7b 0d 20 20 20 20 6c 6f | 63 61 6c 28 2a 46 48 2c |{.    lo|cal(*FH,|
|00001f60| 24 6b 65 79 2c 24 64 69 | 63 74 2c 24 66 6f 6c 64 |$key,$di|ct,$fold|
|00001f70| 29 20 3d 20 40 5f 3b 0d | 20 20 20 20 6c 6f 63 61 |) = @_;.|    loca|
|00001f80| 00 00 00 48 00 09 4d 6f | 6e 61 63 6f 00 65 0d 23 |...H..Mo|naco.e.#|
|00001f90| 0d 23 20 62 79 20 4d 61 | 72 6b 20 42 69 67 67 61 |.# by Ma|rk Bigga|
|00001fa0| 72 0d 23 0d 23 20 00 06 | 00 08 00 3c 00 24 01 dd |r.#.# ..|...<.$..|
|00001fb0| 02 3d 00 3c 00 24 01 dd | 02 3d a6 eb a5 f6 00 00 |.=.<.$..|.=......|
|00001fc0| 1c d0 00 00 1c d0 00 00 | 1b 79 01 00 00 00 00 1e |........|.y......|
|00001fd0| 00 3c 00 24 01 dd 02 3d | 00 3c 00 24 01 dd 02 3d |.<.$...=|.<.$...=|
|00001fe0| 00 00 1b 79 00 00 00 00 | 00 00 00 00 00 00 00 00 |...y....|........|
|00001ff0| 01 00 00 00 01 6e 00 00 | 00 6e 00 00 00 3e 00 41 |.....n..|.n...>.A|
|00002000| 62 20 0f 6e 00 00 00 1c | 00 3e 00 00 4d 50 53 52 |b .n....|.>..MPSR|
|00002010| 00 01 00 0a 03 ed ff ff | 00 00 00 00 00 00 00 00 |........|........|
|00002020| 03 f0 ff ff 00 00 00 4c | 00 47 95 20 00 00 00 00 |.......L|.G. ....|
|00002030| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00002040| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00002050| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00002060| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00002070| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
+--------+-------------------------+-------------------------+--------+--------+