exercise_text.dvi

2007 9 15 17 Windows http://hp.vector.co.jp/authors/va008683/ 1. (Eratosthenes) http://www.faust.fr.bw.schule.de/mhb/eratclass.htm 1.1. ERATOS_2500.BAS, prime_sieve_2500.bas 1

2 2. 2.1.. http://tambara.ms.u-tokyo.ac.jp/tambarabasicprograms.zip 2.2...BAS 2.3.. a, b a b = q r WARIZAN.BAS! WARIZAN.BAS :! a,b : 1000 INPUT PROMPT " a,b ":a,b a,b a, b PRINT LET q=int(a/b) q a/b LET r=mod(a,b) r a b INT(a/b) PRINT a;" ";b;"=";q;" ";r a, b, q, r a, b, q, r PRINT a;"=";b;" ";q;" ";r ; a b = q r a = b q + r 3. BASIC! ERATOS400.BAS! DIM s(400) s DIM p(100) MAT s=zer s(1) s(400) MAT p=zer MAT MATRIX FOR i=2 TO 20 i 2 20

3 FOR j=2*i TO 400 STEP i j 2 i 400 i LET s(j)=1 s(j) NEXT j j NEXT i i LET k=1 k 1 FOR i=2 TO 400 i 2 400 IF s(i)=0 THEN s(i) LET p(k)=i p(k) =i LET k=k+1 k k +1k IF NEXT i i PRINT "400 "; k-1;" " FOR kk=1 TO k-1 kk k 1 PRINT p(kk); NEXT kk kk 3.1. ERATOS400.BAS ERATOS1000000.BAS LET t0=time PRINT "1000000 "; k-1;" ";TIME-t0;" " 3.2. 3.1 ERATOS1000000.BAS FOR j=4 TO 1000000 STEP 2 LET s(j)=1 NEXT j FOR i=3 TO 1000 step 2 FOR j=2*i TO 1000000 STEP i LET s(j)=1 NEXT j NEXT i

4 3.3. 1 1.1 2 2 PRIME_SIEVE.BAS 3.4. r r + 4 ERATOS9999.BAS 3.3 PRIME_SIEVE.BAS 3.2 ERATOS1000000.BAS 1 10000 (r + 4) log 10 log 10 = 2.302585. 4. 3.4 10 (r+4) 9999 10 (r+4) 1 10000 (r + 4) log 10 4.1. n π(n) n lim n π(n) n log n =1 1 log x, m n dx n (0 <m<n) m log x 3.4 n m log n 1 2 0 100, 0 10000, 0 1000000, 0 100000000 n n p(n), log n, dx 3.4 2 log x n dx p(n) log x 2

5 5. 5.1. n 1, n PRIME.BAS 5.2. PrevNextPRIME.BAS 5.3. r r +4 WARIZAN9999.BAS 3.4 ERATOS9999.BAS

6 5.4. 5.1 6. 6.1.. a, b MOD(a,b) a b!congruent.bas INPUT PROMPT " a1,a2, b ":a1,a2,b PRINT a1;" ";a2;" ";MOD(a1+a2,b);"mod" b PRINT a1;" ";a2;" ";MOD(a1-a2,b);"mod" b PRINT a1;" ";a2;" ";MOD(a1*a2,b);"mod" b 6.2.. a, b, y ax y mod b x a, b d au + bv = d u, v y d y = kd x = ku ax y mod b x 1, x 2 a(x 1 x 2 ) 0 mod b a = a 0 d, b = b 0 d x 1 x 2 b 0 a, b d =1 au + bv =1 u, v x = yu ax y mod b x 1, x 2 x 1 x 2 b 0 x<b 6.3.. a, b

7 a>b>0 a b = q r a = b q + r b >r>0 gcd(a, b) =gcd(b, r) b>r>0 gcd(b, r) 0 q a = b q 1 + r 1 b = r 1 q 2 + r 2 r 1 = r 2 q 3 + r 3. r n 1 = r n q n r n n 5n 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040,... a n+1 = a n + a n 1 {a n } x 2 x 1=0 u = 1 5, v = 1+ 5 2 2 a n = ku n + lv n a n+1 = a n + a n 1 a 0 = k + l, a 1 = ku + lv k, l a n a 0, a 1 a n n v n 1+ 5 log 10 = 2 0.20898764 a n n 5! EUCLID1.BAS!! GCD(a,b) INPUT PROMPT "a>b>0 ":a,b PRINT 10 LET q=int(a/b) LET r=mod(a,b) IF r=0 THEN GOTO 30 ELSE GOTO 20 20 PRINT a;"=";b;" ";q;"+";r LET a=b LET b=r GOTO 10 30 PRINT a;" ";b;" ";q r =0 30 20 10

8 a, b au + bv =gcd(a, b) u, v a = b q 1 + r 1, b = r 1 q 2 + r 2 a b q 1 = r 1 b (a b q 1 ) q 2 = r 2, a( 1) + b(1 + q 1 q 2 )=r 2, r 1 = r 2 q 3 + r 3 r 1, r 2 a, b r 3 a, b. r n a, b! EUCLID2.BAS!! ax+by=gcd(a,b) x,y GCD(a,b) INPUT PROMPT "a>b>0 ":a0,b0 PRINT LET s1=0 LET t1=1 LET q=int(a0/b0) LET r=mod(a0,b0) PRINT a0;"=";b0;" ";q;"+";r LET s2=1 LET t2=-q PRINT "(";s2;") ";a0;" (";t2;") ";b0;" ";r LET a=b0 LET b=r 10 LET q=int(a/b) LET r=mod(a,b) IF r =0 THEN GOTO 30 ELSE GOTO 20 20 PRINT a;" ";b;" ";q;" ";r LET s3=s1-q*s2 LET t3=t1-q*t2 PRINT "(";s3;") ";a0;" (";t3;") ";b0;" ";r LET a=b LET b=r LET s1=s2 LET t1=t2 LET s2=s3 LET t2=t3 GOTO 10 30 PRINT a;" ";b;" ";q 7.

9 7.1. a p a p 1 1 mod p a p 1 mod p 234 90916 mod 90917 90916 90916 10110001100100100 90916 = 2 16 +2 14 +2 13 +2 9 +2 8 +2 5 +2 2 = ((((((2 2 +1) 2+1) 2 4 +1) 2+1) 2 3 +1) 2 3 +1) 2 2 a 90916 = (((((((((((((((a 2 ) 2 a) 2 a) 2 ) 2 ) 2 ) 2 a) 2 a) 2 ) 2 ) 2 a) 2 ) 2 ) 2 a) 2 ) 2 a mod 90917 7.1.. n n 2=q 1 r 1 n r 1, q 1 2=q 2 r 2 n r 2 q m 1 2=q m =1 q m r m 1 r m 2 r 2 r 1! BIN_EXPANSION.BAS! INPUT PROMPT " ":n LET nn$="" nn$ 0 50 LET nn$=str$(mod(n,2)) & nn$ n nn$ nn$ LET n=(n- MOD(n,2))/2 IF n>0 THEN GOTO 50 n>0 50 PRINT nn$ nn$

10 7.2.. x n mod a TONTHMODP! TO_THE_NTH_MOD_A.BAS! x, n, a x^n mod a DECLARE EXTERNAL FUNCTION TONTHMODP INPUT PROMPT "x^n mod a x, n, a":x,n,a LET nn$="" 50 LET nn$=str$(mod(n,2)) & nn$ LET n=(n- MOD(n,2))/2 IF n>0 THEN GOTO 50 IF PRINT nn$ PRINT TONTHMODP(x,nn$,a) TONTHMODP EXTERNAL FUNCTION TONTHMODP(x,n$,p) LET y=x FOR i=2 TO LEN(n$) LET y=mod(y*y,p) IF n$(i:i)=str$(1) THEN GOTO 100 ELSE GOTO 130 i 1 100 LET y=mod(x*y,p) GOTO 130 130 NEXT i LET TONTHMODP=y y TONTHMODP FUNCTION 7.2. TO_THE_NTH_MOD_A.BAS p 2 p 1 mod p,..., 100 p 1 mod p 7.3.. p a p 1 1 mod p a n 1 1 mod n n 7.3. TO_THE_NTH_MOD_A.BAS n 2 n 1 mod n, 3 n 1 mod n, 5 n 1 mod n, 7 n 1 mod n, 11 n 1 mod n 2, 3, 5, 7, 11

11 7.4. r r +4 1 2, 3, 5, 7, 11 4 3.4 8. 8.1.. A, B,...!MOJI2SUJI.BAS! INPUT a$ DIM b(len(a$)) FOR k =1 TO LEN(a$) LET b(k)=ord(a$(k:k)) PRINT b(k);","; NEXT k PRINT DIM c$(len(a$)) FOR k =1 TO LEN(a$) LET c$(k)=chr$(b(k)) PRINT c$(k); NEXT k 8.2.. 8.1. p, q pq a p, q a (p 1)(q 1) 1 mod pq 8.2. 7.2 7.2 p, q, a =2,..., 100

12 8.3.. p, q n = pq (p 1)(q 1) e d ed =1 mod(p 1)(q 1) n, e p,q d n a 1, a 2,..., a k b 1 (a 1 ) e mod n, b 2 (a 2 ) e mod n,...,b k (a k ) e mod n b 1, b 2,...,b k b 1, b 2,..., b k c 1 (b 1 ) d mod n, c 2 (b 2 ) d mod n,...,c k (b k ) d mod n c i (b i ) d ((a i ) e ) d (a i ) ed a i c 1, c 2,...,c k a 1, a 2,...,a k 8.4.. 5.2 p, q n = pq e EUCLID2.BAS ed+(p 1)(q 1)r =1 d mod (p 1)(q 1) ANGOU.BAS p, q, n, e, d a$!angou.bas! DECLARE EXTERNAL FUNCTION BIN_EXP$ DECLARE EXTERNAL FUNCTION TONTHMODP LET p=13 LET q=17 LET e=7 LET d=55 LET n=p*q PRINT "n=";n; "e=";e LET a$="i love you." PRINT a$ DIM b(len(a$)) DIM c(len(a$))

13 DIM f(len(a$)) FOR k =1 TO LEN(a$) LET b(k)=ord(a$(k:k)) PRINT b(k);","; NEXT k PRINT LET e$=bin_exp$(e) PRINT e$ FOR k=1 TO LEN(a$) LET c(k)=tonthmodp(b(k),e$,n) PRINT c(k);","; NEXT k PRINT LET d$=bin_exp$(d) PRINT d$ FOR k=1 TO LEN(a$) LET f(k)=tonthmodp(c(k),d$,n) PRINT f(k);","; NEXT k PRINT LET g$="" FOR k=1 TO LEN(a$) LET g$=g$ & CHR$(f(k)) NEXT k PRINT g$ EXTERNAL FUNCTION BIN_EXP$(n) LET nn$="" 50 LET nn$=str$(mod(n,2)) & nn$ LET n=(n- MOD(n,2))/2 IF n>0 THEN GOTO 50 LET BIN_EXP$=nn$ FUNCTION EXTERNAL FUNCTION TONTHMODP(x,n$,p) LET y=x FOR i=2 TO LEN(n$) LET y=mod(y*y,p) IF n$(i:i)=str$(1) THEN GOTO 100 ELSE GOTO 130 100 LET y=mod(x*y,p) GOTO 130

14 130 NEXT i LET TONTHMODP=y FUNCTION n, e