mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Lounge

Reply
 
Thread Tools
Old 2006-02-16, 01:05   #1
pacionet
 
pacionet's Avatar
 
Oct 2005
Italy

3×113 Posts
Default 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
pacionet is offline   Reply With Quote
Old 2006-02-16, 14:04   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26×113 Posts
Default

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.
R.D. Silverman is offline   Reply With Quote
Old 2006-02-16, 14:25   #3
pacionet
 
pacionet's Avatar
 
Oct 2005
Italy

3·113 Posts
Default

Thanks for the hint.
Now I must find some documentation about the fastest algorithm to search.
pacionet is offline   Reply With Quote
Old 2006-02-16, 15:17   #4
Citrix
 
Citrix's Avatar
 
Jun 2003

32·52·7 Posts
Default

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
Citrix is offline   Reply With Quote
Old 2006-02-18, 14:34   #5
pacionet
 
pacionet's Avatar
 
Oct 2005
Italy

33910 Posts
Default

Searching for multimagic squares could be interesting.
Does any software exist ?
pacionet is offline   Reply With Quote
Old 2006-02-18, 16:24   #6
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

32×11×103 Posts
Default

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
xilman is offline   Reply With Quote
Old 2006-02-18, 16:47   #7
Citrix
 
Citrix's Avatar
 
Jun 2003

32·52·7 Posts
Default

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 is offline   Reply With Quote
Old 2006-02-18, 16:52   #8
Citrix
 
Citrix's Avatar
 
Jun 2003

32·52·7 Posts
Default

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
Citrix is offline   Reply With Quote
Old 2006-02-19, 09:20   #9
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

32·11·103 Posts
Default

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
xilman is offline   Reply With Quote
Old 2006-02-19, 10:20   #10
ColdFury
 
ColdFury's Avatar
 
Aug 2002

26·5 Posts
Default

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.
ColdFury is offline   Reply With Quote
Old 2006-02-19, 10:46   #11
Numbers
 
Numbers's Avatar
 
Jun 2005
Near Beetlegeuse

22·97 Posts
Default

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?
Numbers is offline   Reply With Quote
Reply

Thread Tools


All times are UTC. The time now is 13:44.

Sun Nov 29 13:44:24 UTC 2020 up 80 days, 10:55, 3 users, load averages: 1.23, 1.23, 1.26

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.