
Oh well, in that case you have certain advantages.





The only certification that matters is the CodeProject MVP certification





I stumbled upon this new book and I've completed the intro and first chapter.
Classic Computer Science Problems in Python: David Kopec: 9781617295980: Amazon.com: Books[^]
It's actually quite good.
The author writes clearly and makes a point that he backs up with code.
It covers some nice topics that I've been wanting from an introductory level and then proceeding deeper.
* Search algorithms
* Common techniques for graphs
* Neural networks
* Genetic algorithms
* Adversarial search
Wishing For C#
I've been looking for something like this but written in C#.
So, I've begun rewriting the algorithms in C#.
Here are all fibonacci algos rewritten in C#.
I learned quite a bit from rewriting them.
It's a good example to go from recursion to memoization to for loop to yield.
int fibWithRecursion(int n){
if (n < 2){
return n;
}
return fibWithRecursion(n 1) + fibWithRecursion(n2);
}
Dictionary<decimal,decimal> d = new Dictionary<decimal,decimal>();
decimal fib(decimal n){
if (n<2) return n;
if (!d.ContainsKey(n)){
decimal x = fib(n1) + fib(n2);
d.Add(n,x);
}
return d[n];
}
decimal fibViaFor(decimal n){
if (n == 0) return n;
decimal prev = 0;
decimal next = 1;
for (int i = 1; i < n;i++){
decimal oldPrev = prev;
prev = next;
next = oldPrev + next;
}
return next;
}
IEnumerable<decimal> fibViaIterator(decimal n){
decimal prev =0;
decimal next = 1;
for (decimal i = 0; i < n; i++){
yield return prev;
decimal localFib = prev + next;
prev = next;
next = localFib;
}
}
Grab a free copy of LINQPad  The .NET Programmer's Playground[^] and try them out.
Here's the driver code you can use to try each algo:
for (int x = 0; x<15;x++){
Console.Write($"{fibWithRecursion(x)} ");
}
Console.Write("\n");
for (int x = 0; x<15;x++){
Console.Write($"{fib(x)} ");
}
Console.Write("\n");
for (int x = 0; x<15;x++){
Console.Write($"{fibViaFor(x)} ");
}
Console.Write("\n");
foreach (decimal x in fibViaIterator(15)){
Console.Write($"{x} ");
}
Console.Write("\n");
Output looks like the following (each algo produces 1 line):
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377





Certain things functional programming is also an interesting alternative, for example, tail recursion, which looks like recursion but gets compiled into a loop. You don't suffer the performance / call stack penalty of recursion, but the code is (theoretically) cleaner.
Latest Article  A 4Stack rPI Cluster with WiFiEthernet Bridging
Learning to code with python is like learning to swim with those little arm floaties. It gives you undeserved confidence and will eventually drown you.  DangerBunny
Artificial intelligence is the only remedy for natural stupidity.  CDP1802





Marc Clifton wrote: functional programming is also an interesting alternative, for example, tail recursion,
That sounds very interesting and I would like that as the next example in the fibonacci methods (fibonacci solved via functional programming).
How close is that to the yield one (using the iterator)? I think they may be similar but my knowledge is limited. Thanks
IEnumerable<decimal> fibViaIterator(decimal n){
decimal prev =0;
decimal next = 1;
for (decimal i = 0; i < n; i++){
yield return prev;
decimal localFib = prev + next;
prev = next;
next = localFib;
}
}





As an aside there is a method for calculating a fibonacci number without calculating all of the previous numbers in the sequence.
If you are interested it was a method proposed by Dijkstra  scroll down to the middle of (search for 'Can we find a quicker method using only integers?' )
http://www.maths.surrey.ac.uk/hostedsites/R.Knott/Fibonacci/fibFormula.html#section1.3





That's very interesting. Thanks for sharing. Very cool math.





It would be interesting to see your C# examples sidebyside against the same problems solved in F#
"There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult."  C.A.R. Hoare
Home  LinkedIn  Google+  Twitter





F# ( glazes over ) does anyone here use it for a living ?
We can’t stop here, this is bat country  Hunter S Thompson RIP





Dominic Burford wrote: It would be interesting to see your C# examples sidebyside against the same problems solved in F#
Great idea. Maybe someone with knowledge will chime in.





OK but why make the input to fib a decimal ? This way we can do some party tricks such as calling fib(16.646211646837820914214151535M) (just a hair over 2019) but it's unusual.





harold aptroot wrote: OK but why make the input to fib a decimal ?
Oh, yeah. That was just so I could do very large Fib calcs.
It's 16 bytes so you can get a really large value.
You can calculate Fib(132) = 1725375039079340637797070384
That's a big Fib, but no lie!
And, yes, I probably should've done some protective coding and truncated any value after a decimal but this was just for my learning.





OH I like big fibs and I cannot lie, here's a nice trick if you don't mind some BigInteger hackery,
Take some nice prime p such that p ≡ 3 mod 4 (this congruence is not strictly required but makes the next part easier). For example p = 45427892858481394071686190649738831656137145778469793250959984709250004157335359
Then calculate the square root of 5 = BigInteger.ModPow(5, (p + 1) / 4, p) (this simple formula works before p was chosen with p ≡ 3 mod 4).
Calculate a couple of fancy constants,
BigInteger half = BigInteger.ModPow(2, p  2, p);
BigInteger phi = (1 + sqrt5) * half % p;
BigInteger psi = (1 + p  sqrt5) * half % p;
BigInteger invsqrt5 = BigInteger.ModPow(sqrt5, p  2, p);
And then you can use the modular arithmetic version of Binet's Formula,
BigInteger fib(int n)
{
return (BigInteger.ModPow(phi, n, p)  BigInteger.ModPow(psi, n, p) + p) * invsqrt5 % p;
}
Good for n up to around 380 or so, you can use a bigger prime if you want to go higher.
This is more or less a joke of course, if you wanted efficient fibonacci calculations you could also use the optimized version (less redundancy) of matrix powering.





Very cool. Thanks for sharing.





Has anyone heard of SmartXML or used it?





XML ain't smart.
It's the idiot inbred grandchild of PostScript.
I wanna be a eunuchs developer! Pass me a bread knife!





You and Marc are a tag team terror. The math behind it looked interesting.





And here I thought Javascript was evil.
Latest Article  A 4Stack rPI Cluster with WiFiEthernet Bridging
Learning to code with python is like learning to swim with those little arm floaties. It gives you undeserved confidence and will eventually drown you.  DangerBunny
Artificial intelligence is the only remedy for natural stupidity.  CDP1802





You and Mark are a tag team terror. The math behind it looked interesting.





See, now if you'd used PostScript, you could have singlesourced that statement, making allowance for the fact that Marc doesn't know how to spell his name properly.
With XML? Not in a million manhours.
I wanna be a eunuchs developer! Pass me a bread knife!





Mark_Wallace wrote: Marc doesn't know how to spell his name properly
It's spelled Klifton, right?





Bassam AbdulBaki wrote: It's spelled Klifton, right?
I like that. Has a Klingon undertone to it.
Latest Article  A 4Stack rPI Cluster with WiFiEthernet Bridging
Learning to code with python is like learning to swim with those little arm floaties. It gives you undeserved confidence and will eventually drown you.  DangerBunny
Artificial intelligence is the only remedy for natural stupidity.  CDP1802





WTF.
What do you get when you cross a joke with a rhetorical question?
The metaphorical solid rearend expulsions have impacted the metaphorical motorized bladed rotating air movement mechanism.
Do questions with multiple question marks annoy you???





What in the universe is someone calculating where they need 100,000,000 digits?





I suspect that you clicked the wrong comment in the wrong discussion when you wrote your followup.
Nevertheless, I would like to comment on your question:
In my student days (long ago), a fellow student in theoretical physics was working on an analytical model of what happens when two waves collide. He did some numerical simulations, but his results displayed discontinuieties which he traced down to limited precision (72 bits double precision on a Univac mainframe). We wrote him a library for arbitrary precision floating point calculations (they weren't readily available on the Internet in those days), and he set out with 200 decimal digits of precision. This reduced the problems significantly, but not entirely.
Here comes the important stuff: As a student of theoretical physics, math is not hampered by issues like "limited precision". Our fellow student refused to relate to such mundane things. After two others have failed to make him understand that when adding the elements of a series expansion, it does matter if you add them from the one end or from the other one, I came in as the third one and finally made him accept (I wouldn't say "willingly"...) that adding "from the small end" could make an essential difference. It actually turned out that by adding from the small end, he never needed the exended precision library at all.
Numerical methods, error propagation and stuff like that are certainly not subjects taught to theoretical physicists or anyone else who simply use a computer as a tool to procuce some results. If the users think in math terms, like this student, you need all the precision that can be provided to make computer math behave as closely to real math as possible.
In mathematical theory, you may of course encounter people who really explore extremes of the concepts of numbers. They may even care for integers of 100,000,000 digits  not because they need the precision, but they really handle numbers of that range. The numbers are certainly not needed for any industrial or financial application, only for the number theory. Say, if a mathmatician is studying the possibility of there being a largest possible prime number, he might very well end up in those number ranges.
(Disclaimer: For all I know, it may have been proven that there is no such largest possible prime number. I am not a mathmatician; I simply made it up as a possible example.)



