www.digitalmars.com         C & C++   DMDScript  

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

reply 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
next sibling parent reply "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

answer:
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
parent reply 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
parent reply 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
parent reply 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
parent 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

    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
prev sibling parent BCS <ao pathlink.com> writes:
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