why not?

[pacionet]

I have in mind (for the future, if I have lot, lot, lot time) to think, write and run a small ( but working ) distributed computing project (maybe with BOINC platform). Can you suggest me some possible project yet-to-do ? (any matter: math, games, puzzles, etc. )


Thanks

[R.D. Silverman]

Originally Posted by pacionet

I have in mind (for the future, if I have lot, lot, lot time) to think, write and run a small ( but working ) distributed computing project (maybe with BOINC platform). Can you suggest me some possible project yet-to-do ? (any matter: math, games, puzzles, etc. )


Thanks

An open problem is whether every integer can be written as the difference
or two powers. Clearly, numbers that are odd or 0 mod 4 always have a trivial
representation. Numbers that are 2 mod 4 are the problem.

There are no known solutions to x^a - y^b = N for a,b >= 2 and
N = 6,14,50, ..... etc.

[pacionet]

Thanks for the hint.
Now I must find some documentation about the fastest algorithm to search.

[Citrix]

This might be interesting
http://www.mersenneforum.org/showthread.php?t=4631

I personally decided, there is no solution to the problems mentioned in the thread I have posted, and that is why did not pursue it, but if you are interested you could have a go at it.

Citrix

[pacionet]

Searching for multimagic squares could be interesting.
Does any software exist ?

[xilman]

Originally Posted by pacionet

I have in mind (for the future, if I have lot, lot, lot time) to think, write and run a small ( but working ) distributed computing project (maybe with BOINC platform). Can you suggest me some possible project yet-to-do ? (any matter: math, games, puzzles, etc. )


Thanks

Here's one from computer science.

Consider a fairly simple but useful library routine and a target machine architecture. The problem is to find the optimal implementation, where you optimize for some quantity --- usually execution speed, but perhaps memory usage or code size.

One approach is to write all possible programs, reject those which don't implement the routine, and chose the optimal of the remainder. This simple approach undergoes combinatorial explosion, so the research project is to find a better method.

A routine that I'd like to see (and, probably, Bob) is something that can find the smallest prime factor of a small integer as fast as possible. Assume for concreteness that factor(N) is only called when N is known to be composite, that N < 2^128, and that you are generating code for x86-64 machines.

You may wish to prototype your DC project with something easier. Perhaps finding an optimal way of counting the number of set bits in a sequence of integers, the length of the sequence either being fixed (for an easier problem) or given as a parameter (rather harder). Alternatively, find some other function which you may believe to be more tractable and/or more interesting.

Should be challenging.

Paul

[Citrix]

Paul,
You idea seems interesting. But what language do you use for the code? Suppose you come up with a function then how do you compile it, execute it to test it?

Could you provide me some insight on how one could approach the implemention such a project. The idea is great but the implementation seems complex.

Citrix

[Citrix]

Originally Posted by pacionet

Searching for multimagic squares could be interesting.
Does any software exist ?

No none exists, you will have to write one yourself. It is not very hard to write.It will not take very long to write, but making it BOINC compatible will take alot of time.

Anyway, there is alot of litreature on the web on the magic square of squares(3X3), you could easily write a program to test if one exists and then distribute it.


Citrix

[xilman]

Originally Posted by Citrix

Paul,
You idea seems interesting. But what language do you use for the code? Suppose you come up with a function then how do you compile it, execute it to test it?

Could you provide me some insight on how one could approach the implemention such a project. The idea is great but the implementation seems complex.

Citrix

Here's a very simple mechanism. I do not claim it is the best.

Write a program that, in order:

writes an assembly language program to a file;
calls the system-supplied assembler to create an executable program;
runs that program as a sub-process and measures its execution speed when fed test data.

The third stage, of course, must check that the results of the sub-process are correct.

All the above presumes that the optimizing program is running on the same architecture as the routine to be optimized. That may be a valid assumption, especially in a massively parallel implementation where it allows optimal library routines to be found for many architectures in parallel and with efficiency proportional to the market share of each architecture.


Paul



Paul

[ColdFury]

Originally Posted by xilman

Here's a very simple mechanism. I do not claim it is the best.

Write a program that, in order:

writes an assembly language program to a file;
calls the system-supplied assembler to create an executable program;
runs that program as a sub-process and measures its execution speed when fed test data.

The third stage, of course, must check that the results of the sub-process are correct.

All the above presumes that the optimizing program is running on the same architecture as the routine to be optimized. That may be a valid assumption, especially in a massively parallel implementation where it allows optimal library routines to be found for many architectures in parallel and with efficiency proportional to the market share of each architecture.


Paul



Paul

Another approach is to adopt a *very* simple virtual machine instruction set, and generate opcodes from there and "simulate" their execution.

I don't know if this idea will get anywhere though, the problem space is huge, and 99.9999% of all possible solutions will generate garbage. I don't see any obvious automated methods to generate valid programs without resorting to blind search.

[Numbers]

Originally Posted by R.D. Silverman

There are no known solutions to x^a - y^b = N for a,b >= 2 and N = 6,14,50, ..... etc.

I am clearly missing something here. I make 3^5 - 15^2 = 18

Is that not a solution?