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 = [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
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