mersenneforum.org why not?
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2006-02-16, 01:05 #1 pacionet     Oct 2005 Italy 3×113 Posts why not? 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
2006-02-16, 14:04   #2
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 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.

 2006-02-16, 14:25 #3 pacionet     Oct 2005 Italy 3×113 Posts Thanks for the hint. Now I must find some documentation about the fastest algorithm to search.
 2006-02-16, 15:17 #4 Citrix     Jun 2003 110001010112 Posts 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
 2006-02-18, 14:34 #5 pacionet     Oct 2005 Italy 3×113 Posts Searching for multimagic squares could be interesting. Does any software exist ?
2006-02-18, 16:24   #6
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

2×72×109 Posts

Quote:
 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

 2006-02-18, 16:47 #7 Citrix     Jun 2003 157910 Posts 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
2006-02-18, 16:52   #8
Citrix

Jun 2003

110001010112 Posts

Quote:
 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

2006-02-19, 09:20   #9
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

2×72×109 Posts

Quote:
 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

2006-02-19, 10:20   #10
ColdFury

Aug 2002

32010 Posts

Quote:
 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.

2006-02-19, 10:46   #11
Numbers

Jun 2005
Near Beetlegeuse

22×97 Posts

Quote:
 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?