Dedekind Sums
02-26-2024, 02:28 PM
Post: #1
 Eddie W. Shore Senior Member Posts: 1,585 Joined: Dec 2013
Dedekind Sums
Definition

The Dedekind Sum is defined as follows:

Let P and Q be relatively prime integers, that is GCD(P, Q) = 1.

Then S is the Dedekind sum as:

S = Σ( ((I ÷ Q)) × ((P × I ÷ Q)), for I=1 to Q)

The double parenthesis around the terms I ÷ Q and P × I ÷ Q signify a custom function:

(( X )) =
0, if X is an integer
X – FLOOR(X) – 1/2, if X is not an integer

If X is positive, X – INTG(X) – 1/2

HP Prime: DEDEKIND
Code:
EXPORT DEDEKIND(p,q) BEGIN // 2024-02-21 EWS LOCAL s,i,a,b; // Calculation IF CAS.gcd(p,q)==1 THEN s:=0; FOR i FROM 1 TO q DO a:=i/q; IF FP(a)==0 THEN a:=0; ELSE a:=a-FLOOR(a)-0.5; END; b:=p*i/q; IF FP(b)==0 THEN b:=0; ELSE b:=b-FLOOR(b)-0.5; END; s:=s+a*b;  END; RETURN s;  ELSE RETURN "p and q are not relatively prime."; END;  END;

P = 2, Q = 17: 0.4705882353
P =14, Q = 57: -0.8187134503

Sources

Shipp, R. Dale. “Table of Dedekind Sums” Journal of Research of the National Bureau of Standards-B. Mathematics and Mathematical Physics Vol. 69B, No 4, October-December 1965 https://nvlpubs.nist.gov/nistpubs/jres/6...59_A1b.pdf
Retrieved February 21, 2024

Weisstein, Eric W. "Dedekind Sum." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/DedekindSum.html
Retrieved February 18, 2024
02-26-2024, 09:47 PM (This post was last modified: 02-26-2024 09:49 PM by johnb.)
Post: #2
 johnb Member Posts: 243 Joined: Feb 2014
RE: Dedekind Sums
(02-26-2024 02:28 PM)Eddie W. Shore Wrote:
Code:
... a:=a-FLOOR(a)-0.5; ... b:=b-FLOOR(b)-0.5; ... s:=s+a*b;  ... RETURN s;  ...

I don't have a prime, so I don't recall whether it uses a IEEE-754 binary floating point, or a BCD representation, so I may be off-base here. If it's any "binary, mantissa+exponent" representation, then 0.5 is not exactly the same thing as 1/2.

You might squeeze an extra ULP or two out of your answer by computing 'a' and 'b' as twice their values and subtract 1, then return (s/2).

Oops. LOL! Let this be a lesson to my fellow amateur mathematicians: do not attempt what you think are reversible transformations in the real domain when discontinuous functions are involved!

FLOOR(2x) / 2 ≠ FLOOR(x)

[crawling back into my hole in the ground...]

Daily drivers: 15c, 32sII, 35s, 41cx, 48g, WP 34s/31s. Favorite: 16c.
Latest: 15ce, 48s, 50g. Gateway drug: 28s found in yard sale ~2009.
 « Next Oldest | Next Newest »

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