Computing Floor Sum quickly

Revision en6, by ComboGirl, 2022-02-14 12:41:27

I want to compute the sum $$$\left\lfloor \frac{m}{n} \right\rfloor + \left\lfloor \frac{2m}{n} \right\rfloor + \cdots + \left\lfloor \frac{(n-1)m}{n} \right\rfloor = \sum_{k=1}^{n-1} \left\lfloor \frac{km}{n} \right\rfloor$$$ in log time.

I know that when $$$\gcd(m,n) = 1,$$$ this can be viewed as counting lattice points under the line $$$y=\frac{m}{n} x$$$ and by symmetry it's equal to the number of lattice points contained in the entire rectangle, so the sum is equal to $$$\frac{(m-1)(n-1)}{2}.$$$ (When $$$p,q$$$ are prime, the sum is a nice lemma that is used in a proof of Quadratic Reciprocity.)

I'm told that there's a way to think about this that is similar to the Euclidean Algorithm for gcd. Is there a connection to that? Is there a way to generalize the lattice point counting approach for relatively prime $$$m,n$$$?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en8 English ComboGirl 2022-02-14 12:50:31 36
en7 English ComboGirl 2022-02-14 12:43:19 84
en6 English ComboGirl 2022-02-14 12:41:27 13 Tiny change: 'ht\rfloor$\n\nI know' -> 'ht\rfloor$ in log time.\n\nI know'
en5 English ComboGirl 2022-02-14 12:40:42 0 (published)
en4 English ComboGirl 2022-02-14 12:39:43 110
en3 English ComboGirl 2022-02-14 12:38:02 350
en2 English ComboGirl 2022-02-14 12:34:40 63 Tiny change: 'tion to this?' -> 'tion to that?'
en1 English ComboGirl 2022-02-14 12:33:30 314 Initial revision (saved to drafts)