Post Reply 
Most mind-blowing program for your favorite calculator
07-01-2022, 10:06 PM (This post was last modified: 07-03-2022 01:32 PM by Thomas Klemm.)
Post: #28
RE: Most mind-blowing program for your favorite calculator
(07-01-2022 02:12 PM)Pälzer Wrote:  is such a calculation also possible with a solver like the HP-17bII ?

I came up with the following equation:

GCD:GCD=0×(A+B+Σ(I:1:LN(SQRT(5)×A)÷LN((SQRT(5)+1)÷2):1:IF(B<>0:L(R:MOD(A:B))+L(A:B)+L(B:G(R)):0)))+A

To make it more readable we can format it like so:

GCD:GCD=0×(
  A+B+Σ(
    I:
    1:
    LN(SQRT(5)×A)÷LN((SQRT(5)+1)÷2):
    1:
    IF(B<>0:
      L(R:MOD(A:B))+L(A:B)+L(B:G(R)):
      0
    )
  )
)
+A

We can use the Σ function instead of a for-loop.
But gcd is usually implemented with a while-loop:
Code:
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

What should be used as limits in the for-loop?
Of course we could just loop from 1 to a.
But can we do better?

The worst case is to have two consecutive Fibonacci numbers.
From this we can make a better estimate for the needed number of loops.

There's a closed formula:

\(
F_{n}=\frac{\varphi^{n}-\psi^{n}}{\sqrt {5}},
\)

where

\(
\varphi = \frac{1+\sqrt{5}}{2}\approx 1.61803\,39887\ldots
\)

is the golden ratio, and \(\psi\) is its conjugate:

\(
\psi = \frac{1-\sqrt {5}}{2}=1-\varphi =-{1 \over \varphi }\approx -0.61803\,39887\ldots .
\)

But for \(n\) big enough we can ignore \(\psi^{n}\) as it goes to \(0\).

We end up with:

\(
a=\frac{\varphi^{n}}{\sqrt {5}},
\)

This can be solved for \(n\):

\(
n = \frac{\log(\sqrt{5} a)}{\log(\varphi)}
\)

Only if \(B \ne 0\) the remainder \(R\) is calculated:

    IF(B<>0:
      L(R:MOD(A:B))+L(A:B)+L(B:G(R)):
      0
    )

The equivalent code in Python would be:
Code:
if b != 0:
    r = a % b
    a = b
    b = r

But we are not interested in that sum, but only in A.
Thus the expression is multiplied by \(0\) and we end up with:

GCD=0×(…)+A

After verifying the equation you should end up with a menu like this:

[ GCD ][  A  ][  B  ]

Examples

112 A
63 B

GCD
CALCULATING...
GCD=7


144 A
89 B

GCD
CALCULATING...
GCD=1
Find all posts by this user
Quote this message in a reply
Post Reply 


Messages In This Thread
RE: Most mind-blowing program for your favorite calculator - Thomas Klemm - 07-01-2022 10:06 PM



User(s) browsing this thread: 1 Guest(s)