• 0 Posts
  • 3 Comments
Joined 1 year ago
cake
Cake day: June 11th, 2023

help-circle
  • I know I’m probably not changing your mind on this but interested in how you would want the system to be? Regarding your point about being able to rotate the clock so it matches the local solar cycle, suppose we’re in a place where we have 13, at the top of the clock, because that’s when midnight is where we are.

    And let’s say it’s Wednesday 3rd April today. What happens when the clock reaches 13? After 1 second elapses, does your local clock go from Wednesday 3rd April 12:59:59 to…

    a) Wednesday 3rd April 13:00:00 b) Thursday 4th April 13:00:00

    If a) then you have the problem that the date change is now in the middle of the day, and most of the time you can’t even say “what day is it today”. (If 13:00 is midnight, then 00:00, when the date would roll over, would be just before noon.) You have to say today is "Wednesday/Thursday, or “3rd/4th April” because when you wake up it’s Wednesday, but after lunch it becomes Thursday.

    If b) then you have the problem where it may be Thursday 4th April 13:00:00 where you live, but actually it’s not midnight yet somewhere else and so simultaneously it’s Wednesday 3rd April 13:00:00 there. And in fact every location has their own time at which the date rolls over and it’s not even possible to interpret a timestamp unless you have a table that tells you when midnight is for each location.

    Maybe you feel that one or both of these are not really big enough of a problem, or maybe you can think of some other way of dealing with this that I haven’t thought of. And yeah, both of these issues sort of happen already with timezones – the issue in a) happens if you stay up past midnight, but at least it always happens at midnight at not when most people are awake and doing their business. The issue in b) sort of happens already since it can be Wednesday in one place and Thursday in another, but at least the timestamp would always indicate how many hours past the date rollover it is.



  • It’s not that hard to check yourself. Running the following code on my machine, I get that the linear algebra algorithm is already faster than the naive algorithm at around n = 100 or so. I’ve written a more optimised version of the naive algorithm, which is beaten somewhere between n = 200 and n = 500.

    Try running this Python code on your machine and see what you get:

    import timeit
    
    def fib_naive(n):
        a = 0
        b = 1
        while 0 < n:
            b = a + b
            a = b - a
            n = n - 1
        return a
    
    def fib_naive_opt(n):
        a, b = 0, 1
        for _ in range(n):
            a, b = b + a, b
        return a
    
    def matmul(a, b):
        return (
            (a[0][0] * b[0][0] + a[0][1] * b[1][0], a[0][0] * b[0][1] + a[0][1] * b[1][1]),
            (a[1][0] * b[0][0] + a[1][1] * b[1][0], a[1][0] * b[0][1] + a[1][1] * b[1][1]),
        )
    
    def fib_linear_alg(n):
        z = ((1, 1), (1, 0))
        y = ((1, 0), (0, 1))
        while n > 0:
            if n % 2 == 1:
                y = matmul(y, z)
            z = matmul(z, z)
            n //= 2
    
        return y[0][0]
    
    def time(func, n):
        times = timeit.Timer(lambda: func(n)).repeat(repeat=5, number=10000)
        return min(times)
    
    for n in (50, 100, 200, 500, 1000):
        print("========")
        print(f"n = {n}")
        print(f"fib_naive:\t{time(fib_naive, n):.3g}")
        print(f"fib_naive_opt:\t{time(fib_naive_opt, n):.3g}")
        print(f"fib_linear_alg:\t{time(fib_linear_alg, n):.3g}")
    

    Here’s what it prints on my machine:

    ========
    n = 50
    fib_naive:      0.0296
    fib_naive_opt:  0.0145
    fib_linear_alg: 0.0701
    ========
    n = 100
    fib_naive:      0.0652
    fib_naive_opt:  0.0263
    fib_linear_alg: 0.0609
    ========
    n = 200
    fib_naive:      0.135
    fib_naive_opt:  0.0507
    fib_linear_alg: 0.0734
    ========
    n = 500
    fib_naive:      0.384
    fib_naive_opt:  0.156
    fib_linear_alg: 0.112
    ========
    n = 1000
    fib_naive:      0.9
    fib_naive_opt:  0.347
    fib_linear_alg: 0.152