IT討論區(79) 就嚟行行NPL

Ture, the denominator is 2^n so we do not need general fractions. The bit size is F(n) is n * k * log(sqrt(5)). So you can just plug that into big integer arithmetics algorithms to get an upper bound for the time complexity.

Long fixed point is not long enough, you will run into trouble soon for even small value of N. Think about F(1000) for example. If you only want to compute Fibonacci numbers that fit in long fixed point format, you might just use the loop or even precompute them all in a table. There are not that many. 64 bits can store only up to F(93). Some platforms have 128-bit integer but it does not go much further.

Well the question to ask here is not to find the best algorithm to compute the Fibonacci numbers. The question here is how many different ways you can do it. Or whether you can do it with some constraints, like not losing precision.

我個long既意思唔係一個static data structure 而係runtime一開波決定要幾多dp which can be estimated by log(F(n))≈n log phi 或者我個term用big fp 會好啲

其實我面試係會問fibonacci 但係我既焦點有啲唔同 唔只係有幾多個做法去exactly give answer to question 而仲想要solution to problem
所以我會welcome candidate話比我知邊樣係邊方面好啲 唔同既做法之間既比較 甚至係話比我知個problem係ill-defined/out focus
如果可以用10%既力賺到90%既錢 我完全唔介意佢唔識個90%既力 因為佢對define problem既洞見 比起個90%既力 更有價值

If you use BigInteger type in Java or similar arbitrary-sized types in other programming language, you don't need to estimate how much DP in the beginning. BigInteger and similar types grow dynamically. All 5 algorithms above "just work" with arbitrary-sized integer types.

For my interviews, I look at both aptitude and attitude. I want to find candidates with both strong theoretical and practical skills. I also want to find people who really enjoy doing technical work. I don't pay much attention to the candidates future potential for making money for my company. Very often I do general coding and algorithm interviews and sometimes specialist interviews. There are other interviewers usually covering behavioral and system design interviews. I don't enjoy doing those.

Just to interrupt

Up to a few years ago I still used vim as if it was vi, true to my Unix roots. Now I used an internal IDE. I know some people also use other tools like Emacs or Eclipse.

無所謂，黎明都講“Just to say hi”。
https://www.youtube.com/watch?v=HNN0tYb6vtk

如果唔係用Q(sqrt(5))
仍然需要一開始估算要幾多dp 因為需要控制一開始phi同pho既error 先可以控制到final result既error <1
既然都runtime一開始計左error 就可以直接拎一個big fixed point去裝 個data structure之後grow唔grow唔係重點 而且其實一路計一路grow係無意思 grow左個data structure唔代表突然之間多左精度 咪一樣要由頭計返出黎
對無限小數黎講 dp前同dp後既grow係唔同

流程係
1. 估算epsilon by n phi^(n-1) epsilon<1 (first order 想精確啲可以加order 我覺得就咁epsilon除個constant都夠做)
2. 計phi pho such that their erorr<epsilon 放入big fixed point
3. Binet on big fp



Interview黎講 我自己覺得唔睇profit能力係對公司不負責任既表現 因為自由巿場下公司既唯一目的係係合規合理既前提下賺錢
對社會有生產力與否 促進技術進步與否 係巿場既責任
畢竟我唔會覺得自己有能力判斷咩技術咩產品係呢個社會所最需要既野 我會直接依賴巿場去做決定 which就係巿場用錢去inform生產者個巿場到底最需要咩

同埋即使淨係focus係tech 我都唔會覺得我要拎住張checklist去考個candidate 佢有樣做唔到就即刻kick走佢
而係會減分 並且最後考慮埋啲加分位先整體考慮
因為事先定既checklist一定唔係萬能 一定有啲我唔識而人地識既野
如果單單一張現有checklist去filter candidate 咁條team係新諗法方面會弱好多

Windows: vscode
Linux: vi

最近vscode既preview definition 進步左

INT 3

You don't need DP. If a, b are rational numbers, all the real number of the form a + b * sqrt(5) form a ring (let's call it Q(sqrt(5)). In other words, combining any two such number by +, - * or / produces a result of this form also. Note that the golden ratio constants rho and pho are of form.

It is import that a and b above are rational number, not real number. Because a rational number can be represented exactly by computer as p / q, where p and q are both integer. Therefore any number in Q(sqrtt(5)) can be represent by 4 arbitrary-sized integers with no loss of precision. There is no error, period.

The trick here is to evaluate the Binet formula using an abstract data type for numbers in Q(sqrt(5)) instead of a builtin numeric type like double. 1) we know that the Binet formula can be evaluated using only numbers in Q(sqrt(5)) and 2) we know that basic arithmetic operations in Q(sqrt(5)) can be done using integers only.

https://en.wikipedia.org/wiki/Ring_(mathematics)

就係exactly講緊如果唔係用Q(sqrt(5)).......
Q(sqrt(5))個做法 我以為我地前面已經好清楚有共識 就係全部都係interger arithmetic 連fraction都唔需要

我呢到係exactly講緊如果唔用Q(sqrt(5)) 而係想用返fixed point 咁做係點做...
我以為我地一開始已經well known binet起碼有呢兩種做法 同埋用Q(sqrt(5))呢種做法已經無野再需要延申討論...

我以為我地#420同#426已經顯示出我地對點做Q(sqrt(5))已經係討論完 大家都清楚係唔駛fraction 只係做interger arithmetic...

damn it, up mud

Quadratic integer

Windows都應該得 不過要set好啲path
公司用堆神奇makefile所以我費事set了 有需要個時係Linux grep -r
其實我vscode都只係用黎做一個colorful editor 佢啲preview definition係方便 但係我公司啲project dependency唔適合 成日都會搵唔到個header

係咪類似將個plane transform去quadratic field
利申唔識扮識