chris-chan

No language in title because this is more about the algorithms and not about any particular language. I will however use Python in the code examples. I've noticed recently that everybody seems to use the same basic algorithm for computing Fibonacci numbers. This kinda bothers me because there are a few faster algorithms that aren't very complex but for some reason nobody seems to know about them. Fibonacci numbers are often used to teach beginner programmers about recursion and caching or "memoization". The most basic recursive algorithm is something like this: def fib(n): if n == 0: return 0 elif n == 1: return 1 else: return fib(n - 1) + fib(n - 2) This solution is a pretty straightforward translation from the mathematical definition of the Fibonacci sequence. The problem with it is that it is extremely slow because every step recalculates the intermediate values many times. An easy way to make it faster is to use a cache so the function remembers values it has already calculated. In Python this is pretty simple: from functools import cache @cache def fib(n): if n == 0: return 0 elif n == 1: return 1 else: return fib(n - 1) + fib(n - 2) An iterative solution can save some memory space by avoiding the need for a cache, and it can also avoid extra function calls, thus being a bit faster: def fib(n): a, b = 0, 1 while n > 0: a, b = b, a+b n -= 1 return a And this is usually where people usually stop. This is where I would have stopped before about a week ago, when I tried writing this in C using the GNU Multiple Precision arithmetic library (a.k.a. GMP). I was surprised when my basic translation of the iterative version into C was actually a bit slower than the Python version! I decided to read the manual a bit to see if I was doing something wrong when I found GMP's Fibonacci functions. Those ended up being much faster than my simple iterative Python solution. GMP explains the algorithm they use in this manual page. I tried implementing a similar algorithm in Python using some of the identities on the manual page and got a pretty fast Python function (though not as fast as GMP, still much faster than the other Python versions). from functools import cache SMALL_FIBS = [ 0, 1, 1, 2 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610 ] SMALL_FIBS_LEN = len(SMALL_FIBS) @cache def fib(n): if n < SMALL_FIBS_LEN: return SMALL_FIBS[n] k = n//2 fib_k = fib(k) fib_k1 = fib(k - 1) if n&1: # n is odd return (2 * fib_k + fib_k1) * (2 * fib_k - fib_k1) + 2*(-1)**k else: return fib_k * (fib_k + 2 * fib_k1) What I don't get is why this version or something similar isn't more well known? It seems similar to exponentiation by squaring, which is a pretty well known way to quickly calculate powers of numbers. Anyway, I just wanted to share this somewhere other than Reddit lol.

I have a lot of devices in my home. Three Windows 10 based gaming desktop PCs, a Mac mini, a Linux workstation, a Mac Pro, a Power Mac G5, a Power Mac G4, two MacBook Pros, a MacBook Air, an old white MacBook, a Dell XPS 15, and an Alienware laptop. My goal is to be able to back up each of these to a single NAS, and to be able to do so at around 1GBps. Believe it or not, most of my devices can actually hit those kinds of read and write speeds! The old PowerMacs cant, but I'm not that worried about them. Right now my back ups for these are scattered between several external drives, with the important stuff backed up on multiple encrypted USB flash drives. It is a mess! So my questions are: what kind of switch should I buy that can handle 10Gbps? What software can I use that will work on all of these various devices? Once I have backup software set up, how will I handle restoring from those backups when I have a drive failure or an accidental deletion? For the NAS box itself, I was thinking I'd use Ubuntu and zfs, but I'm not sure what hardware platform I should use. I want to be able to use ECC memory, and I'm having a hard time figuring out if any Ryzen motherboards actually, properly support it. I'm also not sure what storage type or brands I should use for maximum reliability, like 2.5 inch SSDs, vs NVMe vs old fashioned spinning hard drives vs Samsung vs Seagate vs WD. So I guess what I'm looking for here are both hardware and software recommendations for someone trying to build a bad ass, high speed, high reliability backup solution for a growing household of devices. I'm not even sure what my budget should be for something like this, but lets just take $10k USD as the hypothetical starting limit.

Update 2: Prime95 failed again with SOC voltage at 1.2125, but the rounding error was not way off this time. Improvement? Max SOC voltage went up to 1.288. Gonna bump it up again.

Update: Prime95 failed with the SOC voltage at 1.20625.

I've built a Threadripper workstation with 128GB of 2933Mhz DDR4, and I have SEM enabled. I'm currently stress testing with Prime95, and I'm getting test failures. The only overclocking I have enabled is the XMP profile for the RAM, and I'm slowly upping the SOC voltage which seems to be helping. I'm concerned that the SOC voltage required is unsafe for longterm use though, as I'm currently set to 1.20625 in the BIOS with LLC set to 1, and I'm seeing the SOC voltage go up to 1.28 in HWMonitor during the stress test. So here are my questions: What is the maximum safe 24/77 voltage for the SOC? For memory? Does anyone have any benchmarks measuring how Transparent SEM affects SOC voltage? How much does memory frequency affect the required SOC voltage? How do I tell the difference between the SOC requiring more voltage, and my RAM requiring more voltage? Update: Prime95 failed with the SOC voltage at 1.20625. Update 2: Prime95 failed again with SOC voltage at 1.2125, but the rounding error was not way off this time. Improvement? Max SOC voltage went up to 1.288. Gonna bump it up again. Update 3: Failed almost immediately with SOC voltage set to 1.21875, gonna drop back to 1.2125 and up the voltage on the DDR4 a bit. Update 4: Prime95 failed with DDR voltage 1.36, but the rounding error was closer! not sure if progress. Max reported DDR4 voltage was 1.368. Gonna up to 1.37 in BIOS and see if that changes anything. Update 5: Prime95 failed almost immediately with DDR voltage at 1.37. I'm resetting the voltage to 1.35 and lower clocks to 2800MHz. Update 6: Prime95 passed the one hour mark with RAM at 2800MHz, 1.35V, and SOC at 1.2125V. Max SOC voltage was 1.288. Next, I will try lowering the SOC voltage. Update 7: Passed one hour again, 1.2V SOC w/ max 1.272, ran running at 2800Mhz 1.35V. Gonna try 2933MHz next with 1.4V Update 8: Failed after 14 minutes. Trying with 1.45V on the memory next. Luckily this kit is Samsung B-die! Setting the SOC LLC to 5 to stop it from spiking so much.

Does anyone know what the performance difference is between these two Threadripper AIOs is? I'm currently using the 360mm version, but I have to have it setup as intake in my case (Corsair Carbide Air 740), and I'm thinking about switching to the 280mm set as exhaust on the top.