## digitalmars.D.learn - Puzzle (8-14)

• Wyverex (5/5) Aug 14 2008 1) Find the smallest x + y + z with integers x y z 0 such that x +
• Steven Schveighoffer (94/99) Aug 14 2008 attempt 1:
• bearophile (36/38) Aug 14 2008 ...
• bearophile (33/33) Aug 14 2008 Using a simple handmade perfect hash the running time of this program be...
• bearophile (6/12) Aug 15 2008 Can be replaced with just:
• BCS (6/11) Aug 14 2008 http://www.dsource.org/projects/scrapple/browser/trunk/bignum/bignum.d
Wyverex <wyverex.cypher gmail.com> writes:
```1)  Find the smallest x + y + z with integers x  y  z  0 such that x +
y, x - y, x + z, x - z, y + z, y - z are all perfect squares.

2)  Develop a bigint type.  should be able to + - * / %.  Should also be
printable!

2.5) make bigfloat.
```
Aug 14 2008
"Steven Schveighoffer" <schveiguy yahoo.com> writes:
```"Wyverex" wrote
1)  Find the smallest x + y + z with integers x  y  z  0 such that x + y,
x - y, x + z, x - z, y + z, y - z are all perfect squares.

attempt 1:

import tango.io.Stdout;
import tango.math.Math;

bool issquare(long x)
{
auto r = sqrt(cast(double)x);
auto lr = cast(long)r;
if(lr * lr == x || (lr + 1) * (lr + 1) == x)
return true;
return false;
}

void main()
{
for(long x = 3; ; x++)
{
for(long i = 1; i * i < x; i++)
{
long y = x - (i * i);
if(issquare(x + y))
{
for(long j = 1; j * j < y; j++)
{
long z = y - (j * j);
if(issquare(y + z) && issquare(x + z) && issquare(x -
z))
{
Stdout(x, y, z).newline;
return;
}
}
}
}
}
}

execution time:

real    0m27.115s
user    0m27.115s
sys     0m0.001s

434657, 420968, 150568

attempt 2 (little bit of cheating, because I know the answer fits within an
int):

bool issquare(int x)
{
auto r = sqrt(cast(double)x);
auto lr = cast(int)r;
if(lr * lr == x || (lr + 1) * (lr + 1) == x)
return true;
return false;
}

void main()
{
int[][int] pairs;

for(int x = 3; ; x++)
{
for(int i = 1; i * i < x; i++)
{
int y = x - (i * i);
if(issquare(x + y))
{
int[] *arr = y in pairs;
if(arr !is null)
{
foreach(z; *arr)
{
if(issquare(x - z) && issquare(x + z))
{
Stdout(x, y, z).newline;
return;
}
}
}
arr = x in pairs;
if(arr is null)
{
pairs[x] = new int[0];
arr = x in pairs;
}
*arr ~= y;
}
}
}
}

runtime:

real    0m11.303s
user    0m11.299s
sys     0m0.005s

When I did this same solution with longs, it was about 23 seconds, so
caching the pairs of possible adjacent values doesn't really save a whole
lot.

2)  Develop a bigint type.  should be able to + - * / %.  Should also be
printable!

Yeah, right. I don't have a week to kill :P

2.5) make bigfloat.

ditto.

-Steve
```
Aug 14 2008
bearophile <bearophileHUGS lycos.com> writes:
```Steven Schveighoffer:
attempt 2 (little bit of cheating, because I know the answer fits within an
int):

...

I have modified your code a little, using a poor's man set to speed up the code:

import std.stdio: putr = writefln;
import std.math: sqrt;

void main() {
int[][int] pairs;
int[int] squares;
for (int i = 1; i < short.max; i++)
squares[i * i] = 0;

for (int x = 3; ; x++) {
for (int i = 1; i * i < x; i++) {
int y = x - (i * i);
if ((x + y) in squares) {
auto arr = y in pairs;
if (arr !is null) {
foreach (z; *arr) {
if ((x - z) in squares && (x + z) in squares) {
putr(x, " ", y, " ", z);
return;
}
}
}

arr = x in pairs;
if (arr is null) {
pairs[x] = new int[0];
arr = x in pairs;
}
*arr ~= y;
}
}
}
}

On my 2 GHz PC it takes 6.97 s to run. I have another trick to try, we'll see
if it works...

Later,
bearophile
```
Aug 14 2008
bearophile <bearophileHUGS lycos.com> writes:
```Using a simple handmade perfect hash the running time of this program becomes
1.3 s on my 2 GHz PC (this also shows why I say that D AAs are slow).

import std.stdio: putr = writefln;

void main() {
auto squares = new int[70_001];
for (int i = 1; i < short.max; i++)
squares[(i * i) % squares.length] = i * i;

int[][int] pairs;
for (int x = 3; ; x++) {
for (int i = 1; i * i < x; i++) {
int y = x - (i * i);
if (squares[(x + y) % squares.length] == x + y) {
auto arr = y in pairs;
if (arr !is null) {
foreach (z; *arr) {
if (squares[(x - z) % squares.length] == (x - z) &&
squares[(x + z) % squares.length] == (x + z)) {
putr(x, " ", y, " ", z);
return;
}
}
}

arr = x in pairs;
if (arr is null) {
pairs[x] = new int[0];
arr = x in pairs;
}
*arr ~= y;
}
}
}
}

Bye,
bearophile
```
Aug 14 2008
bearophile <bearophileHUGS lycos.com> writes:
```Just for reference, all this stuff:

arr = x in pairs;
if (arr is null) {
pairs[x] = new int[0];
arr = x in pairs;
}
*arr ~= y;

Can be replaced with just:

pairs[x] ~= y;

Because arrays in D are structs, not referenced objects.

Bye,
bearophile
```
Aug 15 2008
bearophile <bearophileHUGS lycos.com> writes:
```Python+Psyco version:

from collections import defaultdict
from sys import maxint
from array import array

def main():
pairs = defaultdict(list)
squares_len = 65537
#squares = [0] * squares_len # for Python
squares = array("l", [0]) * squares_len # for Psyco
for i in xrange(1, 1 << 15):
squares[(i * i) % squares_len] = i * i

for x in xrange(3, maxint):
i = 1
while i * i < x:
y = x - i * i
if squares[(x + y) % squares_len] == (x + y):
if y in pairs:
for z in pairs[y]:
if (squares[(x - z) % squares_len] == (x - z) and
squares[(x + z) % squares_len] == (x + z)):
print x, y, z
return
pairs[x].append(y)
i += 1

import psyco; psyco.full()
main()

C++ (MinGW) version:

#include <vector>
#include <ext/hash_map>

using namespace std;
using namespace __gnu_cxx;

int main() {
vector<int> squares(65537, 0);
for (long long i = 1; i < (1 << 15); i++)
squares[(i * i) % squares.size()] = i * i;

typedef hash_map<int, vector<int> > Map;
Map pairs;

for (int x = 3; ; x++)
for (int i = 1; i * i < x; i++) {
int y = x - i * i;
if (squares[(x + y) % squares.size()] == (x + y)) {
Map::iterator arr = pairs.find(y);
if (arr != pairs.end()) {
int nitems = arr->second.size();
for (int j = 0; j < nitems; j++) {
int z = arr->second[j];
if (squares[(x - z) % squares.size()] == (x - z) &&
squares[(x + z) % squares.size()] == (x + z)) {
printf("%d %d %d\n", x, y, z);
return 0;
}
}
}
pairs[x].push_back(y);
}
}

return 0;
}

D version takes 1.29 s (DMD), C++ 1.45 s, Psyco 2.74 s. I don't know why the
C++ version is so slow.

Bye,
bearophile
```
Aug 15 2008
```Reply to wyverex,

2)  Develop a bigint type.  should be able to + - * / %.  Should also
be printable!

http://www.dsource.org/projects/scrapple/browser/trunk/bignum/bignum.d

no %
fixed size at compile time but work(ed) for > 1024 bit
/ only does Bignum/uint and not Bignum/Bignum

2.5) make bigfloat.

no thanks
```
Aug 14 2008