12

## Leaderboard

```
User Language Score
=========================================
Ell C++11 293,619,555
feersum C++11 100,993,667
Ell C++11 78,824,732
Geobits Java 27,817,255
Ell Python 27,797,402
Peter Taylor Java 2,468
<reference> Julia 530
```

## Background

When working on a 2-D grid of integer coordinates, you sometimes want to know whether two vectors (with integer components) have the same magnitude. Of course, in Euclidean geometry the magnitude of a vector `(x,y)`

is given by

```
√(x² + y²)
```

So a naive implementation might compute this value for both vectors and compare the results. Not only does that incur an unnecessary square root computation, it also causes trouble with floating point inaccuracies, which might yield false positives: vectors whose magnitudes are different, but where the significant digits in the floating point representation are all identical.

For the purposes of this challenge, we define a **false positive** as a pair of coordinate pairs `(a,b)`

and `(c,d)`

for which:

- Their squared magnitude is different when represented as 64-bit unsigned integers.
- Their magnitude is identical when represented as 64-bit binary floating point number and computed via a 64-bit square root (as per IEEE 754).

As an example, using 16-bit representations (instead of 64), the smallest^{1} pair of vectors which yields a false positive is

```
(25,20) and (32,0)
```

Their squared squared magnitudes are `1025`

and `1024`

. Taking the square root yields

```
32.01562118716424 and 32.0
```

But in 16-bit floats both of these get truncated to `32.0`

.

Likewise, the smallest^{2} pair yielding a false positive for 32-bit representations is

```
(1659,1220) and (1951,659)
```

_{
1"Smallest" as measured by their 16-bit floating point magnitude.
2"Smallest" as measured by their 32-bit floating point magnitude.
}

Lastly, here are a handful of valid 64-bit cases:

```
(51594363,51594339) and (54792160,48184783)
(54356775,54353746) and (54620742,54088476)
(54197313,46971217) and (51758889,49645356)
(67102042, 956863) and (67108864, 6) *
```

`*`

The last case is one of several with the smallest possible magnitude for 64-bit false positives.

## The Challenge

In less than 10,000 bytes of code, using a single thread, you're to find as many false positives for **64-bit (binary) floating point numbers** in the coordinate range `0 ≤ y ≤ x`

(that is, only within the first octant of the Euclidian plane) such that `x² + y² ≤ 2`

within ^{53}**10 minutes**. If two submissions tie for the same number of pairs, the tie breaker is the actual time taken to find the last of those pairs.

Your program must not use more than **4 GB** of memory at any time (for practical reasons).

It must be possible to run your program in two modes: one which outputs every pair as it finds it, and one which only outputs the number of found pairs at the end. The first will be used to verify the validity of your pairs (by looking at some sample of outputs) and the second will be used for actually timing your submission. Note that the printing must be the *only* difference. In particular, the counting program may not hardcode the number of pairs it *could* find. It must still perform the same loop that would be used to print all the numbers, and only omit the printing itself!

I will test all submissions on my Windows 8 laptop, so please ask in the comments if you want to use some not-too-common language.

Note that pairs must *not* be counted twice under switching of the first and second coordinate pair.

Note also that I will run your process via a Ruby controller, which will kill your process if it hasn't finished after 10 minutes. Make sure to output the number of pairs found by then. You can either keep track of time yourself and print the result just before the 10 minutes elapse, or you just output the number of pairs found sporadically, and I will take the last such number as your score.

As a side comment, it's possible to simultaneously determine whether or not an integer is a perfect square and also compute its precise square root efficiently. The following algorithm is 5x faster than hardware square root on my system (comparing 64-bit unsigned integers to 80-bit long double): http://math.stackexchange.com/questions/41337/efficient-way-to-determine-if-a-number-is-perfect-square/878338#878338

– Todd Lehman – 2014-09-12T19:36:55.063