這是我中一時遇到而解決不了的問題,解決不了不是因為我不懂寫電腦程式,也不是因為這問題本身很困難,而是自己的思想陷入了一個無窮遞歸的循環中跑不出來,因此令我對電腦最初設計者Newman提出的「停止問題(Halting problem)」印象深刻,人腦真的不同電腦。
我當時用的是Dbase作業系統,所以當學到有速算法可立刻分出哪一個數是某數的倍數時,立刻蠢蠢欲動,想寫一個可以分解一個數的所有因子的程式,我的思路是既然一個數最高的因子是它的平方根,因此只要由2開始逐個用速算法測試,直到它最接近它的平方根的整數為止,但是如此一來,數值大小便和要測試的時間成指數比例,8個位的數字是4個位的100部,如何縮短它的所需時間呢?
其中一個思路就是利用遞歸的慨念,在測試某一數字是否它的因子之前,先去測此因子是不是之前已測試的因子之部數,例如要測試101是否為4的部數,只要再測試一下4是不是之前曾測試過的因子2的部數,另外再用邏緝去推斷,既然101不可以被2整除,則它當然不可能被2的部數4來整除;倒過來說,如果它可以被2去整除,則一定要先測試才知道它可不可以被4去整除。
所以最初想的程式的大致結構如下:
輸入1N位的數字,用它的平方根來產生1陣列,以陣列的1來表達可被整除
由2開始到它的平方根(否則會進死迴圈不能停止),
{當陣列對應的值不是1時,
用存在資料庫的樣式來比較輸入之數字是不是可被整除,
如果可以的話把陣列對應的值改成1}
,好像是忘記了什麼?忘記了節省時間的因子再被之前的因子去測試的「偉大發現」!
再補充一下,但如何加上去呢?因為測試數字的次數是定值,而測試因子的次數卻跟因子值而變,我當時不懂如何用Dbase寫出來,因此問題被擱置了!
現在當然是想通了,
輸入1N位的數字,用它的平方根來產生1陣列,以陣列的1來表達可被整除
K由2開始到它的平方根(否則會進死迴圈不能停止),
{
N由2開始直到K的正整數平方根
(當陣列K的值不是1時,
用存在資料庫的樣式來比較輸入之數字是不是可被N整除,
如果可以的話,則:
假如陣列K的值是0,即之前已測試的因子不可以整除輸入的數字,改陣列N的值為0;
並把K加1)
當陣列K的值不是1時,
用存在資料庫的樣式來比較輸入之數字是不是可被整除,
如果可以的話把陣列對應的值改成1;}
不過我當時想的還有更深的一步,有沒有辦法去令電腦自己懂得尋找速算法而不見程式人員輸入呢?我當然懂2,3,4,5,6,9的速算法,但要是其他未知的呢?可不可以寫一個程式去讓電腦先去自己生產一個速算法,然後再利用自己生產的速算法來檢測因子呢?可不可以再推前幾步呢?
(以當時的技術是決沒有可能,但現在可以利用程式天演算法(evolutionary computing)來自己生產程式,所以是絕對可能,但是它可能到再前哪一步呢?相信再進步的電腦也不懂自己找問題來研究吧!)
2009年4月30日 星期四
2009年4月21日 星期二
A program to find all the factors of a number(II)
Last time when I was writing to complete my childhood wish to write a (BASIC) program to find all the factors of a number using heuristic learn from Primary School. However, when I was doing so I has forgotten the true difficult of the program: To shorten the test time, the program would limit to test only the prime factors of the number without knowing which factor are prime. In order to do so, the program will have to test the factor recursively, but I fail to find a way to such write a recursive loop.
Now, I just thought of another method to shorten the search of all factors of a number.
Given a number N,
Define the lower limit of √N as K,
Make an array of K item,
Starting from K,
Check if the K-th element of the Array is zero, otherwise reduce K by 1.
Test if N is divisible by K,
If not reduce K by 1, otherwise:
1.Mark the K as divisible by making the value of K-th item of the array to be 1
2. start the Test for Prime Factor with K as the input.
Test For Prime Factor:
(Define the lower limit of √N as K,
Make an array of K item,
Starting from K,
Test if N is divisible by K,
If not reduce K by 1, otherwise Mark the K as divisible by making the value of K-th item of the array to be 1.)
So, in according to this procedure, if it discover a factor of the N, for instance, 40 is a factor for 1600. Then it would proceed to look up for the factor of 40, which it would arrive at the results: 1,2,4,5,8,10,20. Since 40 is a factor of 1600, and we can logically conclude that the factor of the factor 40 is also a factor of 1600, i.e. 1,2,4,5,8,10,20 are also factors for 1600, which will be skipped for checking in the bigger loop.
Notice the similarity between checking for factor of the number and the checking for factor of the factor. A usual way to save time when writing program is to re-use what is already developed, therefore my first intention is to re-use the same algorithm for checking for factor of the number to check for factor of the factor. Now, wouldn't we able to apply the same logic so we should also checking for factor of the factor of the number to further shorten the process? Should we should also checking for factor of the factor of the factor of the number to further shorten the process?
So in my mind there is no built it mechanism to prevent me from infinite recursion, but when programming in whatever programming language, I need to explicitly state when I need to re-use a sub-procedure. That is the difference between computer and human mind.
Now, I just thought of another method to shorten the search of all factors of a number.
Given a number N,
Define the lower limit of √N as K,
Make an array of K item,
Starting from K,
Check if the K-th element of the Array is zero, otherwise reduce K by 1.
Test if N is divisible by K,
If not reduce K by 1, otherwise:
1.Mark the K as divisible by making the value of K-th item of the array to be 1
2. start the Test for Prime Factor with K as the input.
Test For Prime Factor:
(Define the lower limit of √N as K,
Make an array of K item,
Starting from K,
Test if N is divisible by K,
If not reduce K by 1, otherwise Mark the K as divisible by making the value of K-th item of the array to be 1.)
So, in according to this procedure, if it discover a factor of the N, for instance, 40 is a factor for 1600. Then it would proceed to look up for the factor of 40, which it would arrive at the results: 1,2,4,5,8,10,20. Since 40 is a factor of 1600, and we can logically conclude that the factor of the factor 40 is also a factor of 1600, i.e. 1,2,4,5,8,10,20 are also factors for 1600, which will be skipped for checking in the bigger loop.
Notice the similarity between checking for factor of the number and the checking for factor of the factor. A usual way to save time when writing program is to re-use what is already developed, therefore my first intention is to re-use the same algorithm for checking for factor of the number to check for factor of the factor. Now, wouldn't we able to apply the same logic so we should also checking for factor of the factor of the number to further shorten the process? Should we should also checking for factor of the factor of the factor of the number to further shorten the process?
So in my mind there is no built it mechanism to prevent me from infinite recursion, but when programming in whatever programming language, I need to explicitly state when I need to re-use a sub-procedure. That is the difference between computer and human mind.
2009年4月20日 星期一
A method to approximate the distribution of Prime numner
The idea is following my idea to find all the factors of a number. We know that for a number X, all its factor could be found within square of X. So for N^2, at most it will have N factors, or it will have none except 1 and N.
Since we also know that the factor of 2 has a probability of 1/2 in any natural number; the factor of 3 has a probability of 1/3 in any natural number; thereby the factor N has a probability of 1/N in any natural number. We thus can find the prime by eliminate all known factors.
To count the prime number within range of 1 to N^2 is thus,
[1-(1/2+1/3+1/4+...+1/N-(Any combinations of 1/2,1/3....1/N))]*N
Now consider the various range:
For N=2, the probability of a prime=1-1/2=1/2,
which is 2.
For N=3, the probability of a prime=1-(1/2+1/3-1/6)=1/3,
the prime numbers are 2,3,5,7 which is 4/9;
there is a difference of 1/9.
How come? Because when counting prime numbers, we discount 2,3 because they are also the multiple of 2 and 3.
We can assume that as N become greater, the different would be smaller.
Since we also know that the factor of 2 has a probability of 1/2 in any natural number; the factor of 3 has a probability of 1/3 in any natural number; thereby the factor N has a probability of 1/N in any natural number. We thus can find the prime by eliminate all known factors.
To count the prime number within range of 1 to N^2 is thus,
[1-(1/2+1/3+1/4+...+1/N-(Any combinations of 1/2,1/3....1/N))]*N
Now consider the various range:
For N=2, the probability of a prime=1-1/2=1/2,
which is 2.
For N=3, the probability of a prime=1-(1/2+1/3-1/6)=1/3,
the prime numbers are 2,3,5,7 which is 4/9;
there is a difference of 1/9.
How come? Because when counting prime numbers, we discount 2,3 because they are also the multiple of 2 and 3.
We can assume that as N become greater, the different would be smaller.
訂閱：
文章 (Atom)