因數分解美國總統

因數分解美國總統

Ching-Tang Tseng

Hamilton, New Zealand

16 January 2019

ilikeforth@gmail.com

http://forthfornight.blogspot.com

這是一個展示能從傳統 FORTH 程式叫用 BASIC 式程式的精簡範例‧

題目很簡單：就是把英文字串的碼加總起來，當作該字串的特徵值‧然後，將此值進行澈底地因數分解，最後，列印出以全部質數連乘方式表示的結果‧

提供程式所需資料的來源，採用易於取得的歷任美國總統姓名作為輸入字串‧第 0 筆資料則故意安排為本文作者的姓名‧

為了顯示 FORTH 程式語言的傳承效果，本文刻意採用 35 年前(1983)古聖先賢 Martin Tracy 在其設計之 APPLE II MicroMotion FORTH-79 系統中的創作，來設計字串陣列的結構‧這樣的資料結構，照樣能適用於 35 年後今天正在使用中的 64 位元 Lina64 系統，此一特性凸顯出傳承效果的可貴‧資料結構的設計方法不是僅此一種，採用這樣的設計，純粹只是為了程式使用時很方便所做的選擇‧

由於提供程式使用的資料量有 46 筆，數量稍嫌過大，因此，將資料結構的宣告程式，以及全部輸入的字串資料，安排在另一個提供資料來源的 MartinTracyString.f 檔案中形成‧

從 factorize.f 主程式的內容中可以看得出來，BASIC 式程式的語法，有利於設計數學計算程式，但不利於設計字串輸出方面的程式‧因此，這部份的功能缺陷，仍然需要使用傳統 FORTH 的格式設計程式，然後，再在 BASIC 式程式中，強行利用 RUN 指令來執行 FORTH 指令，以達到彌補功能缺陷目的‧有些答案尾端帶有 * 1 的結果，那是為了美化輸出所做的例外安排‧

原始程式是全用傳統 FORTH 設計的‧原本執行因數分解的部分，由於閱讀困難，不易追蹤，因此，重新改寫成以 BASIC 方式執行的程式，程式便可一目了然‧後續主程式的部分，則完全不需改寫，也是其特色‧

1.      主程式 factorize.f

\ Designer: Ching-Tang Tseng

\ Date: 20190116, Hamilton, New Zealand

FLOAD MartinTracyString.f

VARIABLE LUCKY

5 integers N D P Q R

: FACTORIZE ( n -- )

  [[ N ]] !

  BASIC

\ 10 print " Enter integer number to be factorized "

\ 20 inputi N

30 print " " ; N ; " = "

\ Test if multiple of 2

40 let R = 2

50 let D = N mod R

60 if D = 0 then 80

70 goto 110

80 run R . ." * "

90 let N = N / R

100 goto -50

\ Test if multiple of 3

110 let R = 3

120 let D = N mod R

130 if D = 0 then 150

140 goto 200

150 run R . ." * "

160 let N = N / R

170 goto -120

\ Test of divisors 6P-1 and 6P+1 up to sqr(N)

\ Prime numbers are of the form 6P-1 or 6P+1

200 let Q = sqrt ( N ) + 1

210 for P = 6 to Q step 6

220 let R = P - 1

230 let D = N mod R

240 if D = 0 then 260

250 goto 300

260 run R . ." * "

270 let N = N / R

280 goto -230

300 let R = P + 1

310 let D = N mod R

320 if D = 0 then 340

330 goto 400

340 run R . ." * "

350 let N = N / R

360 goto -310

400 next P

500 if N > 1 then 530

510 run 1 .

520 goto 600

530 run N .

600 end ;

: STRING>PAD>NUMBER  ( addr cnt -- n )

  PAD 80 BLANK

  >R PAD R@ CMOVE

  0

  R> 0

  DO PAD I + C@

     DUP 32 =

         IF DROP ELSE + THEN

  LOOP ;

: MAIN ( -- )

  46 0                          \ 46 is adjustable

  DO

    I USP STRING>PAD>NUMBER LUCKY !

    CR ." ( " I . ." ) " I USP TYPE

    LUCKY @ FACTORIZE CR

  LOOP ;

 
2.      提供數據來源的資料程式 MartinTracyString.f

\ String array designed by Martin Tracy

\ APPLE II MicroMotion FORTH-79, Martin Tracy, 1983

\ Modified to fit AMDX86 ciforth 5.3.0 (Lina64), 20190116

: SARRAY ( cnt n -- )   \ cnt characters/array, total n arrays                 

  CREATE 1+ 0                                   ( cnt n -- )

  DO DUP C, 0 C, DUP ALLOT LOOP DROP

  DOES> DUP C@ 2 + ROT * + 1+ COUNT ;           ( n -- addr cnt )

: S! ( addr1 cnt1 addr2 cnt2 -- )                  

  DROP DUP 2 - C@

  ROT MIN >R DUP 1- R@ SWAP C! R> CMOVE ;

80 100 SARRAY USP

\ 0

S" Ching Tang Tseng"         0 USP S!

\ 1

S" George Washington"        1 USP S!

\ 2

S" John Adams"               2 USP S!

\ 3

S" Thomas Jefferson"         3 USP S!

\ 4

S" James Madison"            4 USP S!

\ 5

S" James Monroe"             5 USP S!

\ 6

S" John Quincy Adams"        6 USP S!

\ 7

S" Andrew Jackson"           7 USP S!

\ 8

S" Martin Van Buren"         8 USP S!

\ 9

S" William Henry Harrison"   9 USP S!

\ 10

S" John Tyler"              10 USP S!

\ 11

S" James K. Polk"           11 USP S!

\ 12

S" Zachary Taylor"          12 USP S!

\ 13

S" Millard Fillmore"        13 USP S!

\ 14

S" Franklin Pierce"         14 USP S!

\ 15

S" James Buchanan"          15 USP S!

\ 16

S" Abraham Lincoln"         16 USP S!

\ 17

S" Andrew Johnson"          17 USP S!

\ 18

S" Ulysses S. Grant"        18 USP S!

\ 19

S" Rutherford B. Hayes"     19 USP S!

\ 20

S" James A. Garfield"       20 USP S!

\ 21

S" Chester A. Arthur"       21 USP S!

\ 22

S" Grover Cleveland"        22 USP S!

\ 23

S" Benjamin Harrison"       23 USP S!

\ 24

S" Grover Cleveland"        24 USP S!

\ 25

S" William McKinley"        25 USP S!

\ 26

S" Theodore Roosevelt"      26 USP S!

\ 27

S" William Howard Taft"     27 USP S!

\ 28

S" Woodrow Wilson"          28 USP S!

\ 29

S" Warren G. Harding"       29 USP S!

\ 30

S" Calvin Coolidge"         30 USP S!

\ 31

S" Herbert Hoover"          31 USP S!

\ 32

S" Franklin D. Roosevelt"   32 USP S!

\ 33

S" Harry S. Truman"         33 USP S!

\ 34

S" Dwight D. Eisenhower"    34 USP S!

\ 35

S" John F. Kennedy"         35 USP S!

\ 36

S" Lyndon B. Johnson"       36 USP S!

\ 37

S" Richard Nixon"           37 USP S!

\ 38

S" Gerald Ford"             38 USP S!

\ 39

S" Jimmy Carter"            39 USP S!

\ 40

S" Ronald Reagan"           40 USP S!

\ 41

S" George H. W. Bush"       41 USP S!

\ 42

S" Bill Clinton"            42 USP S!

\ 43

S" George W. Bush"          43 USP S!

\ 44

S" Barack Obama"                   44 USP S!

\ 45

S" Donald John Trump"       45 USP S!

\ 46

S" Joe Biden"                     46 USP S!

3.      執行結果

ching@center:~$ cd lina64

ching@center:~/lina64$ ./f

AMDX86 ciforth 5.3.0

fload factorize.f

n : ISN'T UNIQUE                                               

D : ISN'T UNIQUE                                               

p : ISN'T UNIQUE                                                

 OK

main

( 0 ) Ching Tang Tseng

1396 = 2 * 2 * 349

( 1 ) George Washington

1659 = 3 * 7 * 79

( 2 ) John Adams

885 = 3 * 5 * 59

( 3 ) Thomas Jefferson

1550 = 2 * 5 * 5 * 31

( 4 ) James Madison

1211 = 7 * 173

( 5 ) James Monroe

1120 = 2 * 2 * 2 * 2 * 2 * 5 * 7 * 1

( 6 ) John Quincy Adams

1518 = 2 * 3 * 11 * 23

( 7 ) Andrew Jackson

1322 = 2 * 661

( 8 ) Martin Van Buren

1420 = 2 * 2 * 5 * 71

( 9 ) William Henry Harrison

2075 = 5 * 5 * 83

( 10 ) John Tyler

927 = 3 * 3 * 103

( 11 ) James K. Polk

1023 = 3 * 11 * 31

( 12 ) Zachary Taylor

1357 = 23 * 59

( 13 ) Millard Fillmore

1535 = 5 * 307

( 14 ) Franklin Pierce

1421 = 7 * 7 * 29 * 1

( 15 ) James Buchanan

1296 = 2 * 2 * 2 * 2 * 3 * 3 * 3 * 3 * 1

( 16 ) Abraham Lincoln

1403 = 23 * 61

( 17 ) Andrew Johnson

1344 = 2 * 2 * 2 * 2 * 2 * 2 * 3 * 7 * 1

( 18 ) Ulysses S. Grant

1397 = 11 * 127

( 19 ) Rutherford B. Hayes

1679 = 23 * 73

( 20 ) James A. Garfield

1405 = 5 * 281

( 21 ) Chester A. Arthur

1459 = 1459

( 22 ) Grover Cleveland

1539 = 3 * 3 * 3 * 3 * 19

( 23 ) Benjamin Harrison

1642 = 2 * 821

( 24 ) Grover Cleveland

1539 = 3 * 3 * 3 * 3 * 19

( 25 ) William McKinley

1515 = 3 * 5 * 101

( 26 ) Theodore Roosevelt

1789 = 1789

( 27 ) William Howard Taft

1731 = 3 * 577

( 28 ) Woodrow Wilson

1389 = 3 * 463

( 29 ) Warren G. Harding

1441 = 11 * 131

( 30 ) Calvin Coolidge

1411 = 17 * 83

( 31 ) Herbert Hoover

1343 = 17 * 79

( 32 ) Franklin D. Roosevelt

1898 = 2 * 13 * 73

( 33 ) Harry S. Truman

1278 = 2 * 3 * 3 * 71

( 34 ) Dwight D. Eisenhower

1778 = 2 * 7 * 127

( 35 ) John F. Kennedy

1233 = 3 * 3 * 137

( 36 ) Lyndon B. Johnson

1475 = 5 * 5 * 59

( 37 ) Richard Nixon

1225 = 5 * 5 * 7 * 7 * 1

( 38 ) Gerald Ford

986 = 2 * 17 * 29

( 39 ) Jimmy Carter

1127 = 7 * 7 * 23 * 1

( 40 ) Ronald Reagan

1198 = 2 * 599

( 41 ) George H. W. Bush

1254 = 2 * 3 * 11 * 19

( 42 ) Bill Clinton

1114 = 2 * 557

( 43 ) George W. Bush

1136 = 2 * 2 * 2 * 2 * 71

( 44 ) Barack Obama

1060 = 2 * 2 * 5 * 53

( 45 ) Donald John Trump

1529 = 11 * 139

(46) Joe Biden

768 = 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 3 * 1 

 OK