Re: question on finding the most efficient quadratic residue filters for Heron triangles

[Charles Greathouse <crgreathouse@gmail.com>]

Z_issquareall tests mod 64, 63, 65, and 11 but uses only one full-length modulus to pull out the residue mod 64*63*65*11. 64 is a very nice one to test as it's nearly free and there are only 12 squares out of 64 total. The others are slower and less efficient but still worthwhile.

I don't understand your choices at all. Testing mod 2565 should't do anything, since you've already tested 3^3 with 7695, 5 with 6460, and 19 with 6859. Am I missing something or misunderstanding what you're doing?

On Tue, Sep 24, 2024 at 7:30 PM American Citizen <website.reader3@gmail.com> wrote:

To all:

I work with triangles, specifically Heron triangles, which have rational
area.

In running over the 3 sides, say a,b,c, I use quadratic residues to help
trim down the testing that has to be done to find rational area.

(1)   area(a,b,c) = sqrt(  (a+b+c) * (-a+b+c) * (a-b+c) * (a+b-c) ) /4

Currently I am testing all 4 parts of the Heron formula, using the
following quadratic residues for n = 7695, 6460, 6859, 2565, and 5130 in
that order.

i.e.

t1 = (a+b+c)

t2 = (-a+b+c)

t3 = (a-b+c)

t4 = (a+b-c)

test ( (t1%7695) * (t2%7695) * (t3%7695) * (t4%7695) % 7695 to see if
the modulo value IS a possible legitimate quadratic residue.

If the values of a,b,c pass this test, then run the next tests
sequentially for 6460, 6859, 2565, and 5130 in that order, if they all
pass, then test the actual area product to see if the square root is
rational. When any failure occurs due to quadratic residue
impossibility, immediately abort those values for a,b,c and do NOT test
the actual area product.

My question to the group is this, is there a specific set of numbers n,
which are most efficient at filtering out values for a,b,c which do NOT
result is rational area Heron triangles? I am looking for a very
efficient way of using quadratic residues to restrict the testing of the
full area inside the Heron formuli, which is rather costly time wise due
to the fact that the values I am working with exceed the bit size of
both long (64 bit) integers and double precision (53 bits)

I did some of my own work, which led me to come up with the 7695,  6460,
6859, 2565, and 5130  values but it would take too much to post why
these values were chosen other than to say that I checked all numbers
from 1 ... 10000 and found the quadratic residues ratios for all these
numbers, and which would have the least legitimate values, which is why
I chose them.

I did a linux gp profile on a very large run finding Heron triangles,
and it showed that most of the time my program was running was spent in
checking the quadratic residue for 7695 inside the function is_area_okay().

  time   seconds   seconds    calls  ms/call  ms/call  name
  39.04    728.82   728.82 2761746433     0.00     0.00
is_area_okay(long const&, long const&, long const&)
  26.82   1229.58   500.76 3751318643     0.00     0.00 reduce_7695()
   8.08   1615.15   150.90 3751318643     0.00     0.00 reduce_five()
   4.99   1708.24    93.09 1239155061     0.00     0.00 reduce_6460()
   1.17   1729.99    21.76                             lgcd(long, long)
   1.11   1750.65    20.66 2193581032     0.00     0.00 reduce_6859()
   0.72   1764.10    13.45 1483633077     0.00     0.00 reduce_2565()
   0.58   1774.83    10.73 reduce_3420()
   0.46   1783.37     8.53 1483633077     0.00     0.00 reduce_5130()

I want to reduce the 26.82% time to a lesser value or find a more
efficient way to filter out values of a,b,c which do NOT result in
rational area

Can GP Pari suggest a very efficient way to filter the a,b,c values? I
want to use GP-Pari to help me develop very efficient C++ code for Heron
triangle searches.

If this topic is slightly askew GP-Pari posts, I apologize for that, but
basically I am trying to speed up calculations for both GP Pari and C++
code.

Randall