/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / scheme / pcscheme / geneva / pcscheme.exe / SAMPLES / E.SW

< prev

next >

MacOS 8.1

Win98

DOS

browse contents

view JSON data

view as text

+--------+-------------------------+-------------------------+--------+--------+
|00000000| 25 2a 20 45 2e 53 57 0d | 0a 25 2a 2a 2a 2a 2a 2a |%* E.SW.|.%******|
|00000010| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|00000020| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|00000030| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|00000040| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|00000050| 2a 2a 0d 0a 25 2a 09 09 | 09 09 09 09 09 09 09 2a |**..%*..|.......*|
|00000060| 0d 0a 25 2a 09 09 50 43 | 20 53 63 68 65 6d 65 2f |..%*..PC| Scheme/|
|00000070| 47 65 6e 65 76 61 20 34 | 2e 30 30 20 53 63 68 65 |Geneva 4|.00 Sche|
|00000080| 6d 65 2d 57 45 42 20 63 | 6f 64 65 09 09 09 2a 0d |me-WEB c|ode...*.|
|00000090| 0a 25 2a 09 09 09 09 09 | 09 09 09 09 2a 0d 0a 25 |.%*.....|....*..%|
|000000a0| 2a 20 28 63 29 20 31 39 | 38 35 2d 31 39 38 38 20 |* (c) 19|85-1988 |
|000000b0| 62 79 20 54 65 78 61 73 | 20 49 6e 73 74 72 75 6d |by Texas| Instrum|
|000000c0| 65 6e 74 73 2c 20 49 6e | 63 2e 20 53 65 65 20 43 |ents, In|c. See C|
|000000d0| 4f 50 59 52 49 47 48 54 | 2e 54 58 54 09 09 2a 0d |OPYRIGHT|.TXT..*.|
|000000e0| 0a 25 2a 20 28 63 29 20 | 31 39 39 32 20 62 79 20 |.%* (c) |1992 by |
|000000f0| 4c 2e 20 42 61 72 74 68 | 6f 6c 64 69 20 26 20 4d |L. Barth|oldi & M|
|00000100| 2e 20 56 75 69 6c 6c 65 | 75 6d 69 65 72 2c 20 55 |. Vuille|umier, U|
|00000110| 6e 69 76 65 72 73 69 74 | 79 20 6f 66 20 47 65 6e |niversit|y of Gen|
|00000120| 65 76 61 09 2a 0d 0a 25 | 2a 09 09 09 09 09 09 09 |eva.*..%|*.......|
|00000130| 09 09 2a 0d 0a 25 2a 2d | 2d 2d 2d 2d 2d 2d 2d 2d |..*..%*-|--------|
|00000140| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00000150| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00000160| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00000170| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2a 0d 0a |--------|-----*..|
|00000180| 25 2a 09 09 09 09 09 09 | 09 09 09 2a 0d 0a 25 2a |%*......|...*..%*|
|00000190| 09 09 09 54 6f 20 43 6f | 6d 70 75 74 65 20 64 69 |...To Co|mpute di|
|000001a0| 67 69 74 73 20 6f 66 20 | 45 09 09 09 09 2a 0d 0a |gits of |E....*..|
|000001b0| 25 2a 09 09 09 09 09 09 | 09 09 09 2a 0d 0a 25 2a |%*......|...*..%*|
|000001c0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|000001d0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|000001e0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|000001f0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00000200| 2d 2d 2d 2d 2d 2d 2a 0d | 0a 25 2a 09 09 09 09 09 |------*.|.%*.....|
|00000210| 09 09 09 09 2a 0d 0a 25 | 2a 20 43 72 65 61 74 65 |....*..%|* Create|
|00000220| 64 20 62 79 3a 20 4c 61 | 72 72 79 20 42 61 72 74 |d by: La|rry Bart|
|00000230| 68 6f 6c 64 69 09 09 44 | 61 74 65 3a 20 31 39 39 |holdi..D|ate: 199|
|00000240| 32 09 09 09 2a 0d 0a 25 | 2a 20 52 65 76 69 73 69 |2...*..%|* Revisi|
|00000250| 6f 6e 20 68 69 73 74 6f | 72 79 3a 09 09 09 09 09 |on histo|ry:.....|
|00000260| 09 09 2a 0d 0a 25 2a 09 | 09 09 09 09 09 09 09 09 |..*..%*.|........|
|00000270| 2a 0d 0a 25 2a 09 09 09 | 09 09 60 60 49 6e 20 6e |*..%*...|..``In n|
|00000280| 6f 6d 69 6e 65 20 6f 6d | 6e 69 70 6f 74 65 6e 74 |omine om|nipotent|
|00000290| 69 69 20 64 65 69 27 27 | 09 2a 0d 0a 25 2a 2a 2a |ii dei''|.*..%***|
|000002a0| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|000002b0| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|000002c0| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|000002d0| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|000002e0| 2a 2a 2a 2a 2a 0d 0a 0d | 0a 5c 64 6f 63 75 6d 65 |*****...|.\docume|
|000002f0| 6e 74 73 74 79 6c 65 5b | 61 34 2c 61 73 74 79 70 |ntstyle[|a4,astyp|
|00000300| 65 64 5d 7b 61 72 74 69 | 63 6c 65 7d 0d 0a 5c 74 |ed]{arti|cle}..\t|
|00000310| 69 74 6c 65 7b 44 69 67 | 69 74 73 20 6f 66 20 65 |itle{Dig|its of e|
|00000320| 7d 0d 0a 5c 61 75 74 68 | 6f 72 7b 4c 61 72 72 79 |}..\auth|or{Larry|
|00000330| 20 42 61 72 74 68 6f 6c | 64 69 20 5c 26 20 68 69 | Barthol|di \& hi|
|00000340| 73 20 67 61 6e 67 7d 0d | 0a 5c 64 61 74 65 7b 5c |s gang}.|.\date{\|
|00000350| 74 6f 64 61 79 7d 0d 0a | 0d 0a 5c 6e 65 77 63 6f |today}..|..\newco|
|00000360| 6d 6d 61 6e 64 7b 5c 70 | 63 73 7d 7b 7b 5c 73 63 |mmand{\p|cs}{{\sc|
|00000370| 20 50 63 53 63 68 65 6d | 65 7d 7d 0d 0a 5c 6e 65 | PcSchem|e}}..\ne|
|00000380| 77 74 68 65 6f 72 65 6d | 7b 6d 75 6c 2d 62 61 73 |wtheorem|{mul-bas|
|00000390| 65 7d 7b 44 65 66 69 6e | 69 74 69 6f 6e 7d 0d 0a |e}{Defin|ition}..|
|000003a0| 0d 0a 5c 62 65 67 69 6e | 7b 64 6f 63 75 6d 65 6e |..\begin|{documen|
|000003b0| 74 7d 0d 0a 5c 6d 61 6b | 65 74 69 74 6c 65 0d 0a |t}..\mak|etitle..|
|000003c0| 0d 0a 57 65 20 67 69 76 | 65 20 68 65 72 65 20 61 |..We giv|e here a|
|000003d0| 20 73 69 6d 70 6c 65 20 | 61 6c 67 6f 72 69 74 68 | simple |algorith|
|000003e0| 6d 20 74 6f 20 63 6f 6d | 70 75 74 65 20 64 69 67 |m to com|pute dig|
|000003f0| 69 74 73 20 6f 66 20 45 | 2e 0d 0a 49 74 73 20 76 |its of E|...Its v|
|00000400| 61 6c 75 65 20 69 73 20 | 6e 61 74 75 72 61 6c 6c |alue is |naturall|
|00000410| 79 20 61 76 61 69 6c 61 | 62 6c 65 20 61 73 20 61 |y availa|ble as a|
|00000420| 20 72 65 61 6c 20 6e 75 | 6d 62 65 72 20 28 74 79 | real nu|mber (ty|
|00000430| 70 65 20 7c 28 65 78 70 | 74 20 31 2e 29 7c 29 2c |pe |(exp|t 1.)|),|
|00000440| 0d 0a 62 75 74 20 69 74 | 20 69 73 20 73 69 67 6e |..but it| is sign|
|00000450| 69 66 69 63 61 6e 74 6c | 79 20 6d 6f 72 65 20 64 |ificantl|y more d|
|00000460| 69 66 66 69 63 75 6c 74 | 20 74 6f 20 64 65 74 65 |ifficult| to dete|
|00000470| 72 6d 69 6e 65 20 6d 6f | 72 65 20 74 68 61 6e 2c |rmine mo|re than,|
|00000480| 20 73 61 79 2c 0d 0a 74 | 68 65 20 31 36 20 64 69 | say,..t|he 16 di|
|00000490| 67 69 74 73 20 6f 66 20 | 36 34 2d 62 69 74 20 72 |gits of |64-bit r|
|000004a0| 65 61 6c 73 2c 20 66 6f | 72 20 77 65 20 6d 75 73 |eals, fo|r we mus|
|000004b0| 74 20 6e 6f 77 20 64 65 | 76 65 6c 6f 70 20 74 68 |t now de|velop th|
|000004c0| 65 20 61 6c 67 6f 72 69 | 74 68 6d 0d 0a 74 6f 20 |e algori|thm..to |
|000004d0| 63 6f 6d 70 75 74 65 20 | 74 68 65 20 65 78 70 6f |compute |the expo|
|000004e0| 6e 65 6e 74 69 61 6c 2e | 0d 0a 0d 0a 49 74 20 69 |nential.|....It i|
|000004f0| 73 20 61 20 6b 6e 6f 77 | 6e 20 66 61 63 74 20 28 |s a know|n fact (|
|00000500| 61 6c 6d 6f 73 74 20 61 | 20 64 65 66 69 6e 69 74 |almost a| definit|
|00000510| 69 6f 6e 20 21 29 20 74 | 68 61 74 0d 0a 24 24 65 |ion !) t|hat..$$e|
|00000520| 5e 78 20 3d 20 5c 6c 69 | 6d 5f 7b 6e 5c 72 69 67 |^x = \li|m_{n\rig|
|00000530| 68 74 61 72 72 6f 77 5c | 69 6e 66 74 79 7d 5c 6c |htarrow\|infty}\l|
|00000540| 65 66 74 28 31 2b 5c 66 | 72 61 63 7b 78 7d 7b 6e |eft(1+\f|rac{x}{n|
|00000550| 7d 5c 72 69 67 68 74 29 | 5e 6e 2e 24 24 0d 0a 49 |}\right)|^n.$$..I|
|00000560| 66 20 77 65 20 74 61 6b | 65 20 24 78 3d 31 24 2c |f we tak|e $x=1$,|
|00000570| 20 77 65 20 67 65 74 20 | 61 20 66 6f 72 6d 75 6c | we get |a formul|
|00000580| 61 20 77 68 69 63 68 20 | 77 65 20 63 61 6e 20 65 |a which |we can e|
|00000590| 78 70 61 6e 64 20 69 6e | 20 61 20 4e 65 77 74 6f |xpand in| a Newto|
|000005a0| 6e 0d 0a 73 65 72 69 65 | 73 3a 0d 0a 24 24 65 20 |n..serie|s:..$$e |
|000005b0| 3d 20 5c 6c 69 6d 5f 7b | 6e 5c 72 69 67 68 74 61 |= \lim_{|n\righta|
|000005c0| 72 72 6f 77 5c 69 6e 66 | 74 79 7d 5c 6c 65 66 74 |rrow\inf|ty}\left|
|000005d0| 28 31 2b 5c 66 72 61 63 | 7b 6e 7d 7b 6e 5c 63 64 |(1+\frac|{n}{n\cd|
|000005e0| 6f 74 20 31 21 7d 2b 0d | 0a 09 5c 66 72 61 63 7b |ot 1!}+.|..\frac{|
|000005f0| 6e 5c 63 64 6f 74 28 6e | 2d 31 29 7d 7b 6e 5e 32 |n\cdot(n|-1)}{n^2|
|00000600| 5c 63 64 6f 74 20 32 21 | 7d 2b 5c 6c 64 6f 74 73 |\cdot 2!|}+\ldots|
|00000610| 5c 72 69 67 68 74 29 3b | 24 24 0d 0a 74 61 6b 69 |\right);|$$..taki|
|00000620| 6e 67 20 74 68 65 20 6c | 69 6d 69 74 20 79 69 65 |ng the l|imit yie|
|00000630| 6c 64 73 20 24 28 6e 2d | 69 29 2f 6e 5c 72 69 67 |lds $(n-|i)/n\rig|
|00000640| 68 74 61 72 72 6f 77 20 | 31 24 2c 20 74 68 75 73 |htarrow |1$, thus|
|00000650| 0d 0a 24 24 65 20 3d 20 | 5c 73 75 6d 5f 7b 69 3d |..$$e = |\sum_{i=|
|00000660| 30 7d 5e 5c 69 6e 66 74 | 79 5c 66 72 61 63 7b 31 |0}^\inft|y\frac{1|
|00000670| 7d 7b 69 21 7d 2e 24 24 | 0d 0a 0d 0a 4f 66 20 63 |}{i!}.$$|....Of c|
|00000680| 6f 75 72 73 65 20 74 68 | 65 20 6e 75 6d 62 65 72 |ourse th|e number|
|00000690| 73 20 69 6e 76 6f 6c 76 | 65 64 20 67 65 74 20 65 |s involv|ed get e|
|000006a0| 78 74 72 65 6d 65 6c 79 | 20 6c 61 72 67 65 20 6f |xtremely| large o|
|000006b0| 72 20 73 6d 61 6c 6c 2c | 20 73 6f 20 77 65 20 6e |r small,| so we n|
|000006c0| 65 65 64 0d 0a 73 6f 6d | 65 20 6b 69 6e 64 20 6f |eed..som|e kind o|
|000006d0| 66 20 63 6f 6d 70 75 74 | 61 74 69 6f 6e 61 6c 20 |f comput|ational |
|000006e0| 74 72 69 63 6b 20 74 6f | 20 6f 62 74 61 69 6e 20 |trick to| obtain |
|000006f0| 61 20 6d 65 61 6e 69 6e | 67 66 75 6c 20 72 65 73 |a meanin|gful res|
|00000700| 75 6c 74 2e 20 54 68 65 | 20 69 64 65 61 0d 0a 69 |ult. The| idea..i|
|00000710| 73 20 74 6f 20 72 65 70 | 72 65 73 65 6e 74 20 24 |s to rep|resent $|
|00000720| 65 24 20 61 73 20 61 20 | 66 69 78 65 64 2d 70 6f |e$ as a |fixed-po|
|00000730| 69 6e 74 20 6d 75 6c 74 | 69 2d 64 69 67 69 74 20 |int mult|i-digit |
|00000740| 6e 75 6d 62 65 72 20 69 | 6e 20 61 20 7b 5c 65 6d |number i|n a {\em|
|00000750| 20 76 61 72 69 61 62 6c | 65 7d 0d 0a 62 61 73 65 | variabl|e}..base|
|00000760| 2c 20 61 6e 64 20 74 68 | 65 6e 20 63 6f 6e 76 65 |, and th|en conve|
|00000770| 72 74 20 69 74 20 74 6f | 20 64 65 63 69 6d 61 6c |rt it to| decimal|
|00000780| 2e 20 4c 65 74 20 75 73 | 20 66 69 72 73 74 20 72 |. Let us| first r|
|00000790| 65 66 69 6e 65 20 74 68 | 65 73 65 20 63 6f 6e 63 |efine th|ese conc|
|000007a0| 65 70 74 73 2e 0d 0a 0d | 0a 41 20 6e 75 6d 62 65 |epts....|.A numbe|
|000007b0| 72 20 24 78 24 20 69 6e | 20 24 62 24 2d 62 61 73 |r $x$ in| $b$-bas|
|000007c0| 65 20 69 73 20 61 20 74 | 75 70 6c 65 20 24 28 5c |e is a t|uple $(\|
|000007d0| 6c 64 6f 74 73 20 78 5f | 31 78 5f 30 2e 78 5f 7b |ldots x_|1x_0.x_{|
|000007e0| 2d 31 7d 5c 6c 64 6f 74 | 73 29 24 20 73 75 63 68 |-1}\ldot|s)$ such|
|000007f0| 20 74 68 61 74 0d 0a 24 | 24 78 20 3d 20 5c 73 75 | that..$|$x = \su|
|00000800| 6d 5f 7b 69 3d 2d 5c 69 | 6e 66 74 79 7d 5e 7b 5c |m_{i=-\i|nfty}^{\|
|00000810| 69 6e 66 74 79 7d 62 5e | 69 5c 63 64 6f 74 20 78 |infty}b^|i\cdot x|
|00000820| 5f 69 2c 24 24 0d 0a 77 | 69 74 68 20 24 30 20 5c |_i,$$..w|ith $0 \|
|00000830| 6c 65 71 20 78 5f 69 20 | 3c 20 62 24 2e 20 54 68 |leq x_i |< b$. Th|
|00000840| 69 73 20 63 61 6e 20 62 | 65 20 75 6e 64 65 72 73 |is can b|e unders|
|00000850| 74 6f 6f 64 20 61 73 20 | 61 20 73 70 65 63 69 61 |tood as |a specia|
|00000860| 6c 20 63 61 73 65 20 77 | 68 65 72 65 20 24 62 24 |l case w|here $b$|
|00000870| 0d 0a 69 74 73 65 6c 66 | 20 69 73 20 61 20 74 75 |..itself| is a tu|
|00000880| 70 6c 65 20 77 68 6f 73 | 65 20 76 61 6c 75 65 73 |ple whos|e values|
|00000890| 20 61 72 65 20 61 6c 6c | 20 69 64 65 6e 74 69 63 | are all| identic|
|000008a0| 61 6c 2e 20 57 65 20 6d | 61 79 20 74 68 65 6e 20 |al. We m|ay then |
|000008b0| 73 74 61 74 65 3a 0d 0a | 5c 62 65 67 69 6e 7b 6d |state:..|\begin{m|
|000008c0| 75 6c 2d 62 61 73 65 7d | 0d 0a 41 20 6e 75 6d 62 |ul-base}|..A numb|
|000008d0| 65 72 20 24 78 24 20 69 | 6e 20 24 7b 5c 62 66 20 |er $x$ i|n ${\bf |
|000008e0| 62 7d 24 2d 62 61 73 65 | 20 69 73 20 61 20 74 75 |b}$-base| is a tu|
|000008f0| 70 6c 65 20 24 28 5c 6c | 64 6f 74 73 20 78 5f 31 |ple $(\l|dots x_1|
|00000900| 78 5f 30 2e 78 5f 7b 2d | 31 7d 5c 6c 64 6f 74 73 |x_0.x_{-|1}\ldots|
|00000910| 29 24 20 73 75 63 68 20 | 74 68 61 74 0d 0a 24 24 |)$ such |that..$$|
|00000920| 20 78 20 3d 20 5c 73 75 | 6d 5f 7b 69 3d 30 7d 5e | x = \su|m_{i=0}^|
|00000930| 7b 5c 69 6e 66 74 79 7d | 5c 6c 65 66 74 28 5c 70 |{\infty}|\left(\p|
|00000940| 72 6f 64 5f 7b 6a 3d 31 | 7d 5e 69 20 62 5f 6a 5c |rod_{j=1|}^i b_j\|
|00000950| 72 69 67 68 74 29 5c 63 | 64 6f 74 20 78 5f 69 0d |right)\c|dot x_i.|
|00000960| 0a 2b 20 78 5f 30 20 2b | 20 5c 73 75 6d 5f 7b 69 |.+ x_0 +| \sum_{i|
|00000970| 3d 2d 5c 69 6e 66 74 79 | 7d 5e 30 5c 6c 65 66 74 |=-\infty|}^0\left|
|00000980| 28 5c 70 72 6f 64 5f 7b | 6a 3d 69 7d 5e 7b 2d 31 |(\prod_{|j=i}^{-1|
|00000990| 7d 62 5f 6a 5e 7b 2d 31 | 7d 5c 72 69 67 68 74 29 |}b_j^{-1|}\right)|
|000009a0| 5c 63 64 6f 74 20 78 5f | 69 24 24 0d 0a 77 69 74 |\cdot x_|i$$..wit|
|000009b0| 68 20 24 30 20 5c 6c 65 | 71 20 78 5f 69 20 3c 20 |h $0 \le|q x_i < |
|000009c0| 62 5f 69 24 2c 20 61 6e | 64 20 6f 66 20 63 6f 75 |b_i$, an|d of cou|
|000009d0| 72 73 65 20 61 6c 6c 20 | 74 68 65 73 65 20 76 61 |rse all |these va|
|000009e0| 6c 75 65 73 20 69 6e 20 | 7b 5c 63 61 6c 20 4e 7d |lues in |{\cal N}|
|000009f0| 2e 0d 0a 5c 65 6e 64 7b | 6d 75 6c 2d 62 61 73 65 |...\end{|mul-base|
|00000a00| 7d 0d 0a 49 66 20 77 65 | 20 74 61 6b 65 20 74 68 |}..If we| take th|
|00000a10| 65 20 62 61 73 65 20 24 | 28 62 5f 69 29 24 20 77 |e base $|(b_i)$ w|
|00000a20| 69 74 68 20 24 62 5f 69 | 20 3d 20 2d 69 24 2c 20 |ith $b_i| = -i$, |
|00000a30| 24 65 24 20 77 69 6c 6c | 20 62 65 20 72 65 70 72 |$e$ will| be repr|
|00000a40| 65 73 65 6e 74 65 64 20 | 61 73 0d 0a 24 31 2e 31 |esented |as..$1.1|
|00000a50| 31 31 31 31 31 5c 6c 64 | 6f 74 73 24 20 41 6c 6c |11111\ld|ots$ All|
|00000a60| 20 77 65 20 68 61 76 65 | 20 74 6f 20 64 6f 20 69 | we have| to do i|
|00000a70| 73 20 63 6f 6e 76 65 72 | 74 20 74 68 69 73 20 74 |s conver|t this t|
|00000a80| 75 70 6c 65 20 69 6e 20 | 61 20 64 65 63 69 6d 61 |uple in |a decima|
|00000a90| 6c 0d 0a 72 65 70 72 65 | 73 65 6e 74 61 74 69 6f |l..repre|sentatio|
|00000aa0| 6e 2e 20 42 75 74 20 74 | 68 61 74 27 73 20 65 6e |n. But t|hat's en|
|00000ab0| 6f 75 67 68 20 6f 66 20 | 63 68 61 74 74 69 6e 67 |ough of |chatting|
|00000ac0| 21 20 6c 65 74 27 73 20 | 67 65 74 20 74 6f 20 63 |! let's |get to c|
|00000ad0| 6f 64 65 2e 0d 0a 20 0d | 0a 54 68 65 20 6e 75 6d |ode... .|.The num|
|00000ae0| 62 65 72 73 20 61 72 65 | 20 72 65 70 72 65 73 65 |bers are| represe|
|00000af0| 6e 74 65 64 20 61 73 20 | 69 6e 66 69 6e 69 74 65 |nted as |infinite|
|00000b00| 20 73 65 71 75 65 6e 63 | 65 73 20 65 78 74 65 6e | sequenc|es exten|
|00000b10| 64 69 6e 67 20 6f 6e 65 | 20 77 61 79 20 75 73 69 |ding one| way usi|
|00000b20| 6e 67 0d 0a 73 74 72 65 | 61 6d 73 20 28 71 75 69 |ng..stre|ams (qui|
|00000b30| 63 6b 2c 20 64 61 73 68 | 20 74 6f 20 79 6f 75 72 |ck, dash| to your|
|00000b40| 20 6d 61 6e 75 61 6c 20 | 74 6f 20 63 68 65 63 6b | manual |to check|
|00000b50| 20 79 6f 75 72 20 6b 6e | 6f 77 6c 65 64 67 65 29 | your kn|owledge)|
|00000b60| 2e 20 54 68 65 20 64 69 | 67 69 74 73 0d 0a 77 69 |. The di|gits..wi|
|00000b70| 6c 6c 20 74 68 65 6e 20 | 62 65 20 63 6f 6d 70 75 |ll then |be compu|
|00000b80| 74 65 64 20 6f 6e 20 64 | 65 6d 61 6e 64 2c 20 77 |ted on d|emand, w|
|00000b90| 69 74 68 20 6e 6f 20 6c | 69 6d 69 74 61 74 69 6f |ith no l|imitatio|
|00000ba0| 6e 20 65 78 63 65 70 74 | 20 6d 65 6d 6f 72 79 20 |n except| memory |
|00000bb0| 61 6e 64 20 74 69 6d 65 | 2e 0d 0a 0d 0a 5c 6e 65 |and time|.....\ne|
|00000bc0| 77 70 61 67 65 0d 0a 54 | 68 69 73 20 72 6f 75 74 |wpage..T|his rout|
|00000bd0| 69 6e 65 20 77 69 6c 6c | 20 63 6f 6e 76 65 72 74 |ine will| convert|
|00000be0| 20 74 68 65 20 24 65 24 | 2d 62 61 73 65 20 6e 75 | the $e$|-base nu|
|00000bf0| 6d 62 65 72 20 7c 78 7c | 20 74 6f 20 64 65 63 69 |mber |x|| to deci|
|00000c00| 6d 61 6c 2e 0d 0a 54 68 | 65 20 62 61 73 69 63 20 |mal...Th|e basic |
|00000c10| 61 6c 67 6f 72 69 74 68 | 6d 20 67 6f 65 73 3a 0d |algorith|m goes:.|
|00000c20| 0a 5c 62 65 67 69 6e 7b | 65 6e 75 6d 65 72 61 74 |.\begin{|enumerat|
|00000c30| 65 7d 0d 0a 5c 69 74 65 | 6d 09 6c 65 61 76 65 20 |e}..\ite|m.leave |
|00000c40| 74 68 65 20 66 69 72 73 | 74 20 64 69 67 69 74 20 |the firs|t digit |
|00000c50| 75 6e 63 68 61 6e 67 65 | 64 2e 0d 0a 5c 69 74 65 |unchange|d...\ite|
|00000c60| 6d 09 6d 75 6c 74 69 70 | 6c 79 20 74 68 65 20 72 |m.multip|ly the r|
|00000c70| 65 73 74 20 62 79 20 31 | 30 2c 20 61 6e 64 20 73 |est by 1|0, and s|
|00000c80| 68 69 66 74 20 69 74 20 | 72 69 67 68 74 20 6f 6e |hift it |right on|
|00000c90| 65 20 70 6f 73 69 74 69 | 6f 6e 2e 0d 0a 09 28 74 |e positi|on....(t|
|00000ca0| 68 69 73 20 6d 61 79 20 | 62 65 20 73 65 65 6e 20 |his may |be seen |
|00000cb0| 61 73 20 61 20 6e 6f 2d | 6f 70 20 69 6e 20 62 61 |as a no-|op in ba|
|00000cc0| 73 65 20 31 30 2e 20 46 | 6f 72 20 69 6e 73 74 61 |se 10. F|or insta|
|00000cd0| 6e 63 65 2c 0d 0a 09 24 | 31 2e 31 31 31 31 31 31 |nce,...$|1.111111|
|00000ce0| 31 31 5c 6c 64 6f 74 73 | 24 20 77 69 6c 6c 20 62 |11\ldots|$ will b|
|00000cf0| 65 63 6f 6d 65 20 24 31 | 2e 30 28 31 30 29 28 31 |ecome $1|.0(10)(1|
|00000d00| 30 29 28 31 30 29 5c 6c | 64 6f 74 73 24 29 2e 0d |0)(10)\l|dots$)..|
|00000d10| 0a 09 55 73 69 6e 67 20 | 74 68 69 73 20 69 6e 69 |..Using |this ini|
|00000d20| 74 69 61 6c 69 7a 61 74 | 69 6f 6e 2c 20 74 68 65 |tializat|ion, the|
|00000d30| 20 64 69 67 69 74 73 20 | 77 69 6c 6c 20 61 6c 77 | digits |will alw|
|00000d40| 61 79 73 20 62 65 20 61 | 20 6c 69 74 74 6c 65 0d |ays be a| little.|
|00000d50| 0a 09 6c 61 74 65 20 69 | 6e 20 74 68 65 20 73 74 |..late i|n the st|
|00000d60| 72 65 61 6d 2c 20 73 6f | 20 77 65 20 68 61 76 65 |ream, so| we have|
|00000d70| 20 73 6f 6d 65 20 74 69 | 6d 65 20 74 6f 20 6d 61 | some ti|me to ma|
|00000d80| 6b 65 20 61 64 6a 75 73 | 74 6d 65 6e 74 73 2e 0d |ke adjus|tments..|
|00000d90| 0a 5c 69 74 65 6d 09 6e | 6f 72 6d 61 6c 69 7a 65 |.\item.n|ormalize|
|00000da0| 20 69 74 3b 20 74 68 61 | 74 20 69 73 2c 20 69 66 | it; tha|t is, if|
|00000db0| 20 74 68 65 20 6e 65 78 | 74 20 64 69 67 69 74 20 | the nex|t digit |
|00000dc0| 69 73 20 74 6f 6f 20 62 | 69 67 2c 20 72 65 64 75 |is too b|ig, redu|
|00000dd0| 63 65 20 69 74 0d 0a 09 | 61 6e 64 20 69 6e 63 72 |ce it...|and incr|
|00000de0| 65 6d 65 6e 74 20 74 68 | 65 20 63 75 72 72 65 6e |ement th|e curren|
|00000df0| 74 20 6f 6e 65 2e 0d 0a | 5c 69 74 65 6d 09 72 65 |t one...|\item.re|
|00000e00| 63 75 72 73 65 20 6f 6e | 20 74 68 65 20 6e 6f 72 |curse on| the nor|
|00000e10| 6d 61 6c 69 7a 61 74 69 | 6f 6e 2e 0d 0a 5c 69 74 |malizati|on...\it|
|00000e20| 65 6d 09 72 65 63 75 72 | 73 65 20 62 61 63 6b 20 |em.recur|se back |
|00000e30| 74 6f 20 28 31 29 2e 0d | 0a 5c 65 6e 64 7b 65 6e |to (1)..|.\end{en|
|00000e40| 75 6d 65 72 61 74 65 7d | 0d 0a 0d 0a 4e 6f 74 65 |umerate}|....Note|
|00000e50| 20 74 68 65 20 7c 28 6e | 6f 72 6d 61 6c 69 7a 65 | the |(n|ormalize|
|00000e60| 20 32 20 2e 2e 2e 29 7c | 20 63 61 6c 6c 73 20 6e | 2 ...)|| calls n|
|00000e70| 6f 72 6d 61 6c 69 7a 65 | 20 77 69 74 68 20 61 20 |ormalize| with a |
|00000e80| 73 6f 75 72 63 65 20 62 | 61 73 65 20 6f 66 20 32 |source b|ase of 2|
|00000e90| 2e 0d 0a 4e 6f 72 6d 61 | 6c 69 7a 65 20 69 6e 63 |...Norma|lize inc|
|00000ea0| 72 65 6d 65 6e 74 73 20 | 74 68 69 73 20 76 61 6c |rements |this val|
|00000eb0| 75 65 20 66 6f 72 20 73 | 75 63 63 65 73 73 69 76 |ue for s|uccessiv|
|00000ec0| 65 20 64 69 67 69 74 73 | 2e 0d 0a 0d 0a 28 64 65 |e digits|.....(de|
|00000ed0| 66 69 6e 65 20 28 63 6f | 6e 76 65 72 74 20 78 29 |fine (co|nvert x)|
|00000ee0| 0d 0a 20 20 28 63 6f 6e | 73 2d 73 74 72 65 61 6d |..  (con|s-stream|
|00000ef0| 0d 0a 20 20 20 20 28 68 | 65 61 64 20 78 29 0d 0a |..    (h|ead x)..|
|00000f00| 20 20 20 20 28 63 6f 6e | 76 65 72 74 20 28 6e 6f |    (con|vert (no|
|00000f10| 72 6d 61 6c 69 7a 65 20 | 32 20 28 63 6f 6e 73 2d |rmalize |2 (cons-|
|00000f20| 73 74 72 65 61 6d 20 30 | 20 28 6d 75 6c 74 20 28 |stream 0| (mult (|
|00000f30| 74 61 69 6c 20 78 29 29 | 29 29 29 29 29 0d 0a 0d |tail x))|)))))...|
|00000f40| 0a 4d 75 6c 74 69 70 6c | 79 20 61 20 6e 75 6d 62 |.Multipl|y a numb|
|00000f50| 65 72 20 62 79 20 31 30 | 2e 0d 0a 28 64 65 66 69 |er by 10|...(defi|
|00000f60| 6e 65 20 28 6d 75 6c 74 | 20 78 29 0d 0a 20 20 28 |ne (mult| x)..  (|
|00000f70| 63 6f 6e 73 2d 73 74 72 | 65 61 6d 20 28 2a 20 31 |cons-str|eam (* 1|
|00000f80| 30 20 28 68 65 61 64 20 | 78 29 29 0d 0a 20 20 20 |0 (head |x))..   |
|00000f90| 20 20 20 20 20 20 20 20 | 20 20 20 20 28 6d 75 6c |        |    (mul|
|00000fa0| 74 20 28 74 61 69 6c 20 | 78 29 29 29 29 0d 0a 0d |t (tail |x))))...|
|00000fb0| 0a 4e 6f 72 6d 61 6c 69 | 7a 65 20 74 68 65 20 6e |.Normali|ze the n|
|00000fc0| 75 6d 62 65 72 2e 20 49 | 66 20 69 74 73 20 73 65 |umber. I|f its se|
|00000fd0| 63 6f 6e 64 20 64 69 67 | 69 74 20 69 73 20 73 6d |cond dig|it is sm|
|00000fe0| 61 6c 6c 20 65 6e 6f 75 | 67 68 2c 20 6c 65 61 76 |all enou|gh, leav|
|00000ff0| 65 20 74 68 65 0d 0a 63 | 75 72 72 65 6e 74 20 6f |e the..c|urrent o|
|00001000| 6e 65 20 75 6e 63 68 61 | 6e 67 65 64 3b 20 6f 74 |ne uncha|nged; ot|
|00001010| 68 65 72 77 69 73 65 20 | 62 75 6d 70 20 75 70 20 |herwise |bump up |
|00001020| 74 68 65 20 63 75 72 72 | 65 6e 74 20 64 69 67 69 |the curr|ent digi|
|00001030| 74 20 61 6e 64 20 64 6f | 77 6e 20 74 68 65 0d 0a |t and do|wn the..|
|00001040| 73 65 63 6f 6e 64 20 6f | 6e 65 2e 20 54 68 65 6e |second o|ne. Then|
|00001050| 20 63 61 6c 6c 20 6e 6f | 72 6d 61 6c 69 7a 65 20 | call no|rmalize |
|00001060| 72 65 63 75 72 73 69 76 | 65 6c 79 20 6f 6e 20 74 |recursiv|ely on t|
|00001070| 68 65 20 74 61 69 6c 2c | 20 69 6e 63 72 65 6d 65 |he tail,| increme|
|00001080| 6e 74 69 6e 67 0d 0a 74 | 68 65 20 73 6f 75 72 63 |nting..t|he sourc|
|00001090| 65 20 62 61 73 65 20 28 | 7c 63 7c 29 2e 0d 0a 0d |e base (||c|)....|
|000010a0| 0a 28 64 65 66 69 6e 65 | 20 28 6e 6f 72 6d 61 6c |.(define| (normal|
|000010b0| 69 7a 65 20 63 20 78 29 | 0d 0a 20 20 28 6c 65 74 |ize c x)|..  (let|
|000010c0| 20 28 28 64 20 28 68 65 | 61 64 20 78 29 29 0d 0a | ((d (he|ad x))..|
|000010d0| 20 20 20 20 20 20 20 20 | 28 65 20 28 68 65 61 64 |        |(e (head|
|000010e0| 20 28 74 61 69 6c 20 78 | 29 29 29 29 0d 0a 20 20 | (tail x|))))..  |
|000010f0| 20 20 28 69 66 20 28 3c | 20 28 2b 20 65 20 39 29 |  (if (<| (+ e 9)|
|00001100| 20 63 29 0d 0a 20 20 20 | 20 20 20 20 20 28 63 6f | c)..   |     (co|
|00001110| 6e 73 2d 73 74 72 65 61 | 6d 20 64 20 28 6e 6f 72 |ns-strea|m d (nor|
|00001120| 6d 61 6c 69 7a 65 20 28 | 2b 20 63 20 31 29 20 28 |malize (|+ c 1) (|
|00001130| 74 61 69 6c 20 78 29 29 | 29 0d 0a 20 20 20 20 20 |tail x))|)..     |
|00001140| 20 20 20 28 63 61 72 72 | 79 20 63 20 28 63 6f 6e |   (carr|y c (con|
|00001150| 73 2d 73 74 72 65 61 6d | 20 64 20 28 6e 6f 72 6d |s-stream| d (norm|
|00001160| 61 6c 69 7a 65 20 28 2b | 20 63 20 31 29 20 28 74 |alize (+| c 1) (t|
|00001170| 61 69 6c 20 78 29 29 29 | 29 29 29 29 0d 0a 0d 0a |ail x)))|))))....|
|00001180| 28 64 65 66 69 6e 65 20 | 28 63 61 72 72 79 20 63 |(define |(carry c|
|00001190| 20 78 29 0d 0a 20 20 28 | 63 6f 6e 73 2d 73 74 72 | x)..  (|cons-str|
|000011a0| 65 61 6d 20 28 2b 20 28 | 68 65 61 64 20 78 29 20 |eam (+ (|head x) |
|000011b0| 28 71 75 6f 74 69 65 6e | 74 20 28 68 65 61 64 20 |(quotien|t (head |
|000011c0| 28 74 61 69 6c 20 78 29 | 29 20 63 29 29 0d 0a 20 |(tail x)|) c)).. |
|000011d0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 28 63 |        |      (c|
|000011e0| 6f 6e 73 2d 73 74 72 65 | 61 6d 20 28 72 65 6d 61 |ons-stre|am (rema|
|000011f0| 69 6e 64 65 72 20 28 68 | 65 61 64 20 28 74 61 69 |inder (h|ead (tai|
|00001200| 6c 20 78 29 29 20 63 29 | 0d 0a 20 20 20 20 20 20 |l x)) c)|..      |
|00001210| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00001220| 20 20 20 20 20 20 28 74 | 61 69 6c 20 28 74 61 69 |      (t|ail (tai|
|00001230| 6c 20 78 29 29 29 29 29 | 0d 0a 0d 0a 54 68 69 73 |l x)))))|....This|
|00001240| 20 70 72 69 6d 69 74 69 | 76 65 20 77 69 6c 6c 20 | primiti|ve will |
|00001250| 62 65 20 75 73 65 66 75 | 6c 20 69 6e 20 65 78 74 |be usefu|l in ext|
|00001260| 72 61 63 74 69 6e 67 20 | 61 20 64 69 67 69 74 20 |racting |a digit |
|00001270| 66 72 6f 6d 20 74 68 65 | 20 73 74 72 65 61 6d 2e |from the| stream.|
|00001280| 0d 0a 7c 28 6e 74 68 20 | 31 30 29 7c 20 77 6f 75 |..|(nth |10)| wou|
|00001290| 6c 64 20 72 65 74 75 72 | 6e 20 74 68 65 20 24 31 |ld retur|n the $1|
|000012a0| 30 5e 7b 74 68 7d 24 20 | 64 69 67 69 74 20 6f 66 |0^{th}$ |digit of|
|000012b0| 20 24 65 24 2e 0d 0a 0d | 0a 28 64 65 66 69 6e 65 | $e$....|.(define|
|000012c0| 20 28 6e 74 68 20 64 69 | 67 69 74 29 0d 0a 20 20 | (nth di|git)..  |
|000012d0| 28 28 6e 61 6d 65 64 2d | 6c 61 6d 62 64 61 20 28 |((named-|lambda (|
|000012e0| 6e 20 64 20 73 29 0d 0a | 20 20 20 20 20 28 69 66 |n d s)..|     (if|
|000012f0| 20 28 3d 20 64 20 30 29 | 20 28 68 65 61 64 20 73 | (= d 0)| (head s|
|00001300| 29 0d 0a 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |)..     |        |
|00001310| 20 20 20 20 28 6e 20 28 | 2d 31 2b 20 64 29 20 28 |    (n (|-1+ d) (|
|00001320| 74 61 69 6c 20 73 29 29 | 29 29 0d 0a 20 20 20 64 |tail s))|))..   d|
|00001330| 69 67 69 74 20 65 29 29 | 0d 0a 0d 0a 48 65 72 65 |igit e))|....Here|
|00001340| 20 77 65 20 63 68 65 61 | 74 20 61 20 6c 69 74 74 | we chea|t a litt|
|00001350| 6c 65 2e 20 24 45 24 20 | 73 68 6f 75 6c 64 20 62 |le. $E$ |should b|
|00001360| 65 20 72 65 70 72 65 73 | 65 6e 74 65 64 20 61 73 |e repres|ented as|
|00001370| 20 24 31 2e 31 31 31 5c | 6c 64 6f 74 73 24 2c 0d | $1.111\|ldots$,.|
|00001380| 0a 62 75 74 20 77 65 20 | 70 72 65 66 65 72 20 74 |.but we |prefer t|
|00001390| 68 65 20 72 65 70 72 65 | 73 65 6e 74 61 74 69 6f |he repre|sentatio|
|000013a0| 6e 20 24 30 2e 32 31 31 | 31 5c 6c 64 6f 74 73 24 |n $0.211|1\ldots$|
|000013b0| 2c 20 61 6c 74 68 6f 75 | 67 68 20 74 68 69 73 20 |, althou|gh this |
|000013c0| 76 69 6f 6c 61 74 65 73 | 0d 0a 6f 75 72 20 64 65 |violates|..our de|
|000013d0| 66 69 6e 69 74 69 6f 6e | 2e 20 54 68 69 73 20 69 |finition|. This i|
|000013e0| 73 20 77 68 79 20 74 68 | 65 20 73 6f 75 72 63 65 |s why th|e source|
|000013f0| 20 62 61 73 65 20 73 74 | 61 72 74 73 20 61 74 20 | base st|arts at |
|00001400| 32 20 69 6e 20 7c 63 6f | 6e 76 65 72 74 7c 2e 0d |2 in |co|nvert|..|
|00001410| 0a 0d 0a 28 64 65 66 69 | 6e 65 20 6f 6e 65 73 20 |...(defi|ne ones |
|00001420| 28 63 6f 6e 73 2d 73 74 | 72 65 61 6d 20 31 20 6f |(cons-st|ream 1 o|
|00001430| 6e 65 73 29 29 0d 0a 28 | 64 65 66 69 6e 65 20 65 |nes))..(|define e|
|00001440| 20 28 63 6f 6e 76 65 72 | 74 20 28 63 6f 6e 73 2d | (conver|t (cons-|
|00001450| 73 74 72 65 61 6d 20 32 | 20 6f 6e 65 73 29 29 29 |stream 2| ones)))|
|00001460| 0d 0a 0d 0a 41 6e 64 20 | 66 69 6e 61 6c 6c 79 20 |....And |finally |
|00001470| 73 6f 6d 65 74 68 69 6e | 67 20 75 73 65 66 75 6c |somethin|g useful|
|00001480| 5c 6c 64 6f 74 73 0d 0a | 0d 0a 28 64 65 66 69 6e |\ldots..|..(defin|
|00001490| 65 20 28 64 69 67 69 74 | 73 20 6e 29 0d 0a 20 20 |e (digit|s n)..  |
|000014a0| 28 6d 61 70 20 6e 74 68 | 20 28 28 6e 61 6d 65 64 |(map nth| ((named|
|000014b0| 2d 6c 61 6d 62 64 61 20 | 28 6c 6f 6f 70 20 66 72 |-lambda |(loop fr|
|000014c0| 6f 6d 20 74 6f 29 0d 0a | 20 20 20 20 20 20 20 20 |om to)..|        |
|000014d0| 20 20 20 20 20 20 28 69 | 66 20 28 3e 20 66 72 6f |      (i|f (> fro|
|000014e0| 6d 20 74 6f 29 20 27 28 | 29 0d 0a 20 20 20 20 20 |m to) '(|)..     |
|000014f0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00001500| 20 20 20 20 20 20 20 20 | 20 28 63 6f 6e 73 20 66 |        | (cons f|
|00001510| 72 6f 6d 20 28 6c 6f 6f | 70 20 28 31 2b 20 66 72 |rom (loo|p (1+ fr|
|00001520| 6f 6d 29 20 74 6f 29 29 | 29 29 0d 0a 20 20 20 20 |om) to))|))..    |
|00001530| 20 20 20 20 20 20 20 20 | 30 20 6e 29 29 29 0d 0a |        |0 n)))..|
|00001540| 0d 0a 54 68 69 73 20 63 | 6f 64 65 20 63 6f 75 6c |..This c|ode coul|
|00001550| 64 20 62 65 20 64 65 73 | 63 72 69 62 65 64 20 61 |d be des|cribed a|
|00001560| 73 20 67 69 76 69 6e 67 | 20 61 6e 20 69 6e 66 69 |s giving| an infi|
|00001570| 6e 69 74 65 20 6e 75 6d | 62 65 72 20 6f 66 20 64 |nite num|ber of d|
|00001580| 69 67 69 74 73 20 69 6e | 0d 0a 61 6e 20 69 6e 66 |igits in|..an inf|
|00001590| 69 6e 69 74 65 20 6e 75 | 6d 62 65 72 20 6f 66 20 |inite nu|mber of |
|000015a0| 74 69 6d 65 2e 20 57 68 | 61 74 20 77 65 20 77 6f |time. Wh|at we wo|
|000015b0| 75 6c 64 20 6c 69 6b 65 | 20 74 6f 20 6b 6e 6f 77 |uld like| to know|
|000015c0| 20 69 73 20 68 6f 77 20 | 6d 75 63 68 20 74 69 6d | is how |much tim|
|000015d0| 65 0d 0a 69 73 20 6e 65 | 65 64 65 64 20 74 6f 20 |e..is ne|eded to |
|000015e0| 63 6f 6d 70 75 74 65 20 | 24 6e 24 20 64 69 67 69 |compute |$n$ digi|
|000015f0| 74 73 2e 0d 0a 0d 0a 4c | 65 74 20 75 73 20 73 75 |ts.....L|et us su|
|00001600| 70 70 6f 73 65 20 24 6b | 24 20 64 69 67 69 74 73 |ppose $k|$ digits|
|00001610| 20 61 72 65 20 75 73 65 | 64 20 69 6e 20 24 65 24 | are use|d in $e$|
|00001620| 2e 20 54 68 65 6e 20 7c | 63 6f 6e 76 65 72 74 7c |. Then ||convert||
|00001630| 20 67 65 74 73 20 63 61 | 6c 6c 65 64 0d 0a 24 6b | gets ca|lled..$k|
|00001640| 24 20 74 69 6d 65 73 2c | 20 63 61 6c 6c 69 6e 67 |$ times,| calling|
|00001650| 20 69 74 73 65 6c 66 20 | 7c 6e 6f 72 6d 61 6c 69 | itself ||normali|
|00001660| 7a 65 7c 20 24 6b 24 20 | 74 69 6d 65 73 2e 20 54 |ze| $k$ |times. T|
|00001670| 68 65 20 66 61 63 74 20 | 74 68 61 74 20 61 20 30 |he fact |that a 0|
|00001680| 20 67 65 74 73 0d 0a 69 | 6e 73 65 72 74 65 64 20 | gets..i|nserted |
|00001690| 69 6e 20 74 68 65 20 73 | 74 72 65 61 6d 20 69 6e |in the s|tream in|
|000016a0| 20 7c 63 6f 6e 76 65 72 | 74 7c 20 73 68 6f 77 73 | |conver|t| shows|
|000016b0| 20 75 73 20 74 68 61 74 | 20 24 6b 5c 61 70 70 72 | us that| $k\appr|
|000016c0| 6f 78 20 6e 2f 32 24 2e | 0d 0a 54 68 65 6e 20 74 |ox n/2$.|..Then t|
|000016d0| 68 65 20 72 75 6e 6e 69 | 6e 67 20 74 69 6d 65 20 |he runni|ng time |
|000016e0| 69 73 20 24 4f 28 6e 5e | 32 29 24 2e 0d 0a 5c 65 |is $O(n^|2)$...\e|
|000016f0| 6e 64 7b 64 6f 63 75 6d | 65 6e 74 7d 0d 0a       |nd{docum|ent}..  |
+--------+-------------------------+-------------------------+--------+--------+