[sub-project] Perfect cuboid

Fehler und Wünsche zum Projekt yoyo@home
Bugs and wishes for the project yoyo@home

Re: [sub-project] Perfect cuboid

Unread postby x3mEn » 31.03.2011 12:36

Robert Gerbicz wrote:
x3mEn wrote:For a more realictic view, we can ask even the next:
How many odd numbers less than 2^64 has only 4k+1 primes in its decomposition to divisors, if the largest divisor is less than 2^32 (2^40 or any other number, that we will set as a goal)


Why not simulate it? For 100000 random numbers gives 595 such numbers. So we can expect approx. 595/100000*2^64~10^17 numbers to test. It's a pretty huge. Only for one number on average you should check thousands of triangle pairs.

I'll recheck your result later.

Some notes to your estimate.
First, we no need to check g = prime 4k+1, because in this case g² has only 2 decompositions to a sum of squares. So we can skip these diagonals.
Second, primes p=4k+1, 2^64/25 < p < 2^64/5 produce diagonals with only 2 divisors: p and (5 or 13 or 17)
The square of these diagonals g^2 has only 4 decompositions to a sum of squares, at the same time one of them is trivial: g² = 0² + g²
Thus a huge amount of primes p=4k+1, 2^64/25 < p < 2^64/5 produce diagonal with only 1 triangle of pairs.
The chance that this 1 triangle of pairs will produce a perfect cuboid is miserable.
And all efforts will be spend not on diagonals checking, but simply to the bust of primes.

FYI. g = 5*p, where p = x²+y² produce the next 4 decompositions:
g² = 0² + (5p)²
g² = (y² - x²)² + (2xy)²
g² = (6xy - 4y² + 4x²)² + (8xy + 3y² - 3x²)²
g² = (8xy - 3y² + 3x²)² + (6xy + 4y² - 4x²)²
Maybe someone can prove that the last three are not a perfect cuboid pairs?

First decomposition we'll skip. Other three first must be ordered in way g² = k² + l², where k < l.
After that, these three must be ordered by k acsending.
Top 2 pairs make
g² = a² + f²
g² = b² + e²
The last equation contains c and d in unknown order (maybe c < d, maybe c > d).
Thus our the only task is to check, that, for example
a² + b² = d²
we can do this check in a different ways.
a, b, d are 64-bit integers, thus we can't calculate a sum of squares directly.
First, we can check, for example that
byte(byte(a)²) + byte(byte(b)²) = byte(byte(d)²)
byte returns the last 8 bit of number.
Thus if equation is correct for 64 bits, it will be correct for the last 8 bits too.
This routine is very fast and very effective.

If check is passed, after that I apply more strong condition
integer(integer(a)²) + integer(integer(b)²) = integer(integer(d)²)
integer returns the last 32 bits.

And only after passing and this check, I apply the check, which use sqrt:
a = sqrt(d - b) sqrt(d + b)
The argument of sqrt is a number <2^65.
sqrt is real class numbers function.
Especially to point that the result must be 64 bit I use in Delphi the next trick:
a = sqrt(d - b + 0.0) sqrt(d + b + 0.0)
Thus 64 bit extended multiplied by another 64 bit extended. The result is 64 bit extended too.
Thus it's very important to sqrt correctly figured at least 48 characters and multiplication of extended must have 64 bit precision.
It's one of the weak sides of my program.
Because I don't exactly know what is an actual precision of these functions from the math library, what Delphi uses.
They say that sqrt(extended) returns extended, but how accurate this extended is calculated, I don't know.
The same about an accurancy of multiply operation.
If someone could advise something better, I'll make it.

There are some other trivial checks before the sqrt is used but I don't want to spend your time to these details.
x3mEn
PDA-Benutzer
PDA-Benutzer
 
Posts: 43
Joined: 20.03.2011 22:23

Re: [sub-project] Perfect cuboid

Unread postby Robert Gerbicz » 31.03.2011 15:47

x3mEn wrote:Some notes to your estimate.
First, we no need to check g = prime 4k+1, because in this case g² has only 2 decompositions to a sum of squares. So we can skip these diagonals.

You are funny, when I make an estimation then in the next reply: no, you don't need to check some numbers and lower my original estimation by 0.0001 percentage. This leads to nowhere.
In fact my code skipped that numbers where g has got a prime divisor p>2^32 , as you requested. So the suggested speedup is to skip the 4k+1 primes<2^32.

When I code the first two things that is in my mind: is it a good program, is it solve the problem? What is the running time for the average case/best case? Ram?
Robert Gerbicz
PDA-Benutzer
PDA-Benutzer
 
Posts: 56
Joined: 08.06.2010 19:06

Re: [sub-project] Perfect cuboid

Unread postby x3mEn » 01.04.2011 18:46

I have rechecked the estimation.

First, High(Int64)=2^63-1 in Delphi
There are ~2^61 numbers 4k+1 between 1 and 2^63-1
I've got 100000 random numbers 4k+1 between 1 and 2^63-1

Unfortunately, [table] BB-codes or monospace font choise are absent on this forum (or engine, I don't know),
so I'll try to show the result here as is:
=======================================
2^N| 4K+1 | ?_4K+1 | Primes | Max_Div|
=======================================
_0_|______0_|______0_|______0_|______0_|
_1_|______0_|______0_|______0_|______0_|
_2_|______0_|______0_|______0_|______0_|
_3_|______0_|______0_|______0_|______0_|
_4_|______0_|______0_|______0_|______0_|
_5_|______0_|______0_|______0_|______0_|
_6_|______0_|______0_|______0_|______0_|
_7_|______0_|______0_|______0_|______0_|
_8_|______0_|______0_|______0_|______0_|
_9_|______0_|______0_|______0_|______0_|
10_|______0_|______0_|______0_|______0_|
11_|______0_|______0_|______0_|______0_|
12_|______0_|______0_|______0_|______0_|
13_|______0_|______0_|______0_|______0_|
14_|______0_|______0_|______0_|______0_|
15_|______0_|______0_|______0_|______0_|
16_|______0_|______0_|______0_|______0_|
17_|______0_|______0_|______0_|______0_|
18_|______0_|______0_|______0_|______0_|
19_|______0_|______0_|______0_|______0_|
20_|______0_|______0_|______0_|______0_|
21_|______0_|______0_|______0_|______1_|
22_|______0_|______0_|______0_|______0_|
23_|______0_|______0_|______0_|______3_|
24_|______0_|______0_|______0_|______6_|
25_|______0_|______0_|______0_|______3_|
26_|______0_|______0_|______0_|______9_|
27_|______0_|______0_|______0_|_____19_|
28_|______0_|______0_|______0_|_____19_|
29_|______0_|______0_|______0_|_____34_|
30_|______0_|______0_|______0_|_____49_|
31_|______0_|______0_|______0_|_____58_|
32_|______0_|______0_|______0_|_____80_|
33_|______0_|______0_|______0_|____115_|
34_|______0_|______0_|______0_|____154_|
35_|______0_|______0_|______0_|____184_|
36_|______0_|______0_|______0_|____204_|
37_|______0_|______0_|______0_|____257_|
38_|______0_|______0_|______0_|____334_|
39_|______0_|______0_|______0_|____327_|
40_|______0_|______0_|______0_|____384_|
41_|______0_|______0_|______0_|____476_|
42_|______0_|______0_|______0_|____600_|
43_|______1_|______0_|______0_|____606_|
44_|______0_|______0_|______0_|____669_|
45_|______0_|______0_|______0_|____681_|
46_|______1_|______0_|______0_|____682_|
47_|______1_|______0_|______0_|____752_|
48_|______2_|______0_|______0_|____686_|
49_|______5_|______1_|______0_|____765_|
50_|_____18_|______7_|______3_|____708_|
51_|_____24_|______8_|______1_|____757_|
52_|_____48_|_____22_|______7_|____787_|
53_|_____89_|_____24_|______6_|____809_|
54_|____202_|_____54_|_____13_|____819_|
55_|____360_|_____94_|_____38_|____845_|
56_|____815_|____204_|_____70_|____845_|
57_|___1571_|____412_|____135_|____883_|
58_|___3113_|____801_|____282_|____868_|
59_|___6216_|___1519_|____564_|____607_|
60_|__12647_|___3151_|____997_|____573_|
61_|__24844_|___6104_|___1974_|______0_|
62_|__50043_|__12294_|___3947_|______0_|
=======================================
___|_100000_|__24695_|___8037_|__16658_|
=======================================

how to read this table:
1st column - the power N of 2, defines the bounds for group: 2^N .. 2^(N+1)-1
All other columns figure the amount of numbers in the next categories:
1) quantity of all 4k+1 numbers
2) quantity of 4k+1 numbers, which are a product of 4k+1 prime dividers only
3) quantity of primes on the 2nd group
4) quantity of numbers of the 2nd group in distribution on their biggest divider

Thus, if I havn't made a mistake,
1) quantity of primes is signifacant (8% of all 4k+1 numbers, or 30% of all 4k+1 that has only 4k+1 dividers)
2) my estimation of quantity of all diagonals between 1 and 2^63-1 is 16658/100000*2^61 ~ 3.8*10^17
The lion part of them are produced with a participation of very big dividers, which are unreachable anyway.
For example, 96.7% of all these diagonals are produced with a participation of primes bigger than 2^35.
90.82% - bigger than 2^39
3) my estimation of quantity of all diagonals between 1 and 2^63-1 with the largest divider less than 2^32 is 201/100000*2^61 ~ 4.6*10^15

Source code attached.
Attachments
estimate.zip
(1.23 KiB) Downloaded 86 times
x3mEn
PDA-Benutzer
PDA-Benutzer
 
Posts: 43
Joined: 20.03.2011 22:23

Re: [sub-project] Perfect cuboid

Unread postby x3mEn » 08.04.2011 13:59

Robert Gerbicz, do you agree with my estimate? Or what your silence means?
I can assume that you have made certain conclusions for yourself and this topic is no longer interesting for you, but then you may say about it, agree?
My estimation is 100 times less then your. I think it's important, who, me or you, have made a mistake, isn't it?
x3mEn
PDA-Benutzer
PDA-Benutzer
 
Posts: 43
Joined: 20.03.2011 22:23

Re: [sub-project] Perfect cuboid

Unread postby Death » 02.12.2011 15:47

Is there any progress? :roll:
Image
Death
Taschenrechner
Taschenrechner
 
Posts: 11
Joined: 14.04.2010 08:32

Re: [sub-project] Perfect cuboid

Unread postby Randall » 26.03.2012 22:16

Since I am the person who has searched for all cuboids with the smallest edge <= 22 billion+ and growing now, I would like to offer some input to this discussion.

Just searching the space diagonal is going to miss all the body cuboids.

My search finds all 3 types of cuboids, so that nothing is missed.

I know that we're trying to find the perfect cuboid, but it isn't that simple. You need a very fast square root op on the computer. Right now the cuda devices that I am working on cannot even handle 128 bit code yet.

Randall
Randall
Fingerzähler
Fingerzähler
 
Posts: 1
Joined: 26.03.2012 22:13

Re: [sub-project] Perfect cuboid

Unread postby fwjmath » 06.04.2012 23:46

@Randall,

I am very interested by your work and how it progresses. Would you mind to share your method and your code? If it is embarrassingly parallel, or at least somehow parallel, maybe the community here can still make a subproject out of it that might greatly push the search forward.

And another rather irrelevant question, how fast should that square root be and for what range of numbers?

fwjmath.
fwjmath
PDA-Benutzer
PDA-Benutzer
 
Posts: 56
Joined: 19.10.2010 15:26

Re: [sub-project] Perfect cuboid

Unread postby x3mEn » 16.09.2012 19:18

Actually from the time of my last trial to push up my idea there were some changes in approach.
In general it is: factorization + decomposition of any 4k+1 number instead of composing a number as a product of 4k+1 primes
It leads to the next improvements:
1) we can sequentially run up to high values
2) we can do batch processing for mass number exclusion and factorization

In details:

1) we take some range of numbers (this is our Work Unit). For example:
[WU]
Ini=9223372036854765805
Fin=9223372036854775805
and generate a pool of 4k+1 numbers from the range

2) we organize loop for i from 3 up to sqrt(Fin) step 2
for every number i from loop we calculate first odd value j that i*j >= Ini
while i*j <= Fin we do loop for j step 2 and
- exclude numbers if not(i is 4k+1 form & j is 4l+1 form) (Sieve of Eratosthenes)
- else we memorize i and change the value of number N to N/i (if i<=sqrt(N))
After full loop for i we get that some numbers in the range will be
- or excluded
- or factorized by primes 4k+1 form
The 2nd group is our candidates.

3) We gather all factors we meet during factorization of this group and begin their decomposition into the sum of 2 squares
After this step batch processing is completed.

4) For every factorized number from the range we build all its different decompositions into the sum of 2 squares

5) We check all triples of pairs for:
- perfect cuboids
- almost perfect cuboids of 2 types:
-- where the space diagonal and two of the three face diagonals are integers
-- where the space diagonal and two of the three edges are integers
x3mEn
PDA-Benutzer
PDA-Benutzer
 
Posts: 43
Joined: 20.03.2011 22:23

Re: [sub-project] Perfect cuboid

Unread postby x3mEn » 02.08.2017 11:45

Hello guys!

From the time of my last trial many things have changed.
First, this spring I at last learned C (pure C, not C++) and translate my ideas and previous developments on C language.
After 2 monthes of alpha-testing I can say we (me and some of my team mates) achieved a huge progress on Perfect and almost Perfect Cuboids search.
Just to illustrate my words: for now we spent 20468 hours of machine time, executed and verified 22000 tasks, achieved 11'294'187'638'059 high threshold for body diagonal and found:
0 Perfect cuboids
56686 Edge cuboids
97773 Face cuboids
0 Complex Perfect cuboids
236139 Imaginary cuboids
1171794 Twilight cuboids

Regarding the terms.
I accepted Randall terms for Body, Edge and Face cuboids which mean almost Perfect cuboid in natural numbers with only one irrational side (Body, Edge or Face diagonal respectively).
But Randall also infected me by an idea of searching Perfect and almost Perfect cuboids in complex numbers.
So, after investigation I found to be useful to give names for 3 new types of complex cuboids (except Complex Perfect cuboid which is obvious, I guess):
Imaginary cuboid means almost Perfect cuboid with only Edge(s) in complex numbers.
Twilight cuboid means almost Perfect cuboid with Edge(s) and Face diagonal(s) in complex numbers, but with Body diagonal in natural numbers.
Midnight cuboid means almost Perfect cuboid with Edge(s), Face diagonal(s) and Body diagonal in natural numbers.

From the method of searching I found, there are available to search:
- entire Edge cuboids
- entire Face cuboids
- special forms of Imaginary cuboid + Imaginary cuboids as derrivative forms of Face cuboids
- Twilight cuboids as derrivative forms of Edge, Face and Imaginary cuboids
- Midnight cuboids were dropped out because (from my opinion) they are primitive derrivative of entire all previous kinds of cuboids.

I developed and continue to improve 2 fork versions of application:
1) pure app with minimal memory requirements
2) "fast and furious" app with different factorization method with elavated requirements to memory values
Every version was compiled for:
- windows x86
- windows x86_64
- linux x86
- linux x86_64

Regarding the speed of application. It depends on CPU, it's obvious, but to illustrate I'll show the statistics for Intel Core i5-3570K @ 3.4 (4 cores loaded):
Code: Select all
Research Range borders  : from 14179465920467 to 14180514234323 step 4
Total amount of Numbers : 262078464

Elapsed time            : 00:31:26.062
Candidates investigated : 43979128
Perfect Cuboids found   : 0
Edge Cuboids found      : 1
Face Cuboids found      : 1
Complex Cuboids found   : 0
Imaginary Cuboids found : 3
Twilight Cuboids found  : 15

So, for now, I investigated app speed for different ranges, using the "fast and furious" app version, we need ~2.5 mln years of machine time to complete and achieve the theoretical limit of my application — 2^63.
After that we could say that if Perfect cuboid exist, its body diagonal should be greater than 2^63.
And also we will have found all Edge and Face cuboids with body diagonal less than 2^63.
Sounds delicious, isn't it?

And now I'll show the results (all found by this task cuboids):
Code: Select all
E,14179858245605,65724623395,6572820402012,√157862092102226504626841856,6573148999013,12564490114141,14179705925700
T,√157862092102226504626841856,6572820402012i,65724623395i,14179858245605,6573148999013i,12564490114141,14179705925700
T,6572820402012,√-157862092102226504626841856,65724623395i,14179858245605,12564490114141i,6573148999013,14179705925700
T,65724623395,√-157862092102226504626841856,6572820402012i,14179858245605,14179705925700i,6573148999013,12564490114141
F,14180035564565,3355146851904,9244680126060,10215296744653,9834689676396,10752176429875,√189816398214486916575214009
T,10215296744653,9244680126060i,3355146851904i,14180035564565,9834689676396i,10752176429875,√189816398214486916575214009
T,9244680126060,10215296744653i,3355146851904i,14180035564565,10752176429875i,9834689676396,√189816398214486916575214009
T,3355146851904,10215296744653i,9244680126060i,14180035564565,√-189816398214486916575214009,9834689676396,10752176429875
I,14180035564565,3355146851904i,9834689676396,10752176429875,9244680126060,10215296744653,√212330419010169559992064441
T,10752176429875,9834689676396i,3355146851904,14180035564565,9244680126060i,10215296744653,√212330419010169559992064441
T,9834689676396,10752176429875i,3355146851904,14180035564565,10215296744653i,9244680126060,√212330419010169559992064441
T,3355146851904,14180035564565i,9834689676396,10752176429875,10215296744653i,9244680126060i,√212330419010169559992064441
I,10752176429875,9244680126060i,9834689676396,10215296744653,3355146851904,√18888176948149441592966809,14180035564565
T,10215296744653,9834689676396i,9244680126060,10752176429875,3355146851904i,√18888176948149441592966809,14180035564565
T,9834689676396,10215296744653i,9244680126060,10752176429875,√-18888176948149441592966809,3355146851904,14180035564565
T,9244680126060,10752176429875i,9834689676396,10215296744653,√-18888176948149441592966809,3355146851904i,14180035564565
I,14180041244825,√-141385324359813363909241344,12690237914200,13469103746937,4433600563784,6327039701625,18505644924313
T,13469103746937,12690237914200i,√141385324359813363909241344,14180041244825,4433600563784i,6327039701625,18505644924313
T,12690237914200,13469103746937i,√141385324359813363909241344,14180041244825,6327039701625i,4433600563784,18505644924313
T,√141385324359813363909241344,14180041244825i,12690237914200,13469103746937,6327039701625i,4433600563784i,18505644924313

How to read this?
(E,F,I,T) — this is cuboid type, it's obvious, next 7 numbers are:
Body diagonal, 3 Edges sorted from smallest, 3 Face diagonals (sorted from biggest).
As you can see, 1st imaginary cuboid (with 14180035564565 body diagonal) is a derrivative of the previous Face cuboid with the same body diagonal.
Every Edge, Face and Imaginary cuboids produce 3 additional Twilight cuboids.

If someone from the Rechenkraft.net team will read this and will be interested to start a new one yoyo sub-project, please contact me for details.
I'm also open for discussion about math basis of research.
Please join https://t.me/joinchat/BrFEbg7IlqMFl4PBRSdEBA if you are interested on app alpha-testing or just for discuss an approach.
x3mEn
PDA-Benutzer
PDA-Benutzer
 
Posts: 43
Joined: 20.03.2011 22:23

Re: [sub-project] Perfect cuboid

Unread postby x3mEn » 15.08.2017 22:03

28'000 tasks done
26'339 core*hours = 1097 core*days = 3 core*years spent
17'578'355'938'459 = ~ 2^44 achieved
—-------------------------------------------------
0 Perfect cuboids found
64'187 Edge cuboids found
111'237 Face cuboids found
0 Complex Perfect cuboids found
268'326 Imaginary cuboids found
1'331'250 Twilight cuboids found
x3mEn
PDA-Benutzer
PDA-Benutzer
 
Posts: 43
Joined: 20.03.2011 22:23

Re: [sub-project] Perfect cuboid

Unread postby x3mEn » 08.09.2017 18:37

Manual crunch:
40'730 tasks done
38'115 hours = 1588 days = 4,348 years spent
30'359'586'957'394 achieved
—-------------------------------------------------
0 perfect cuboids found
74'706 edge cuboids found
129'983 face cuboids found
0 perfect complex cuboids found
313'393 imaginary cuboids found
1'554'246 twilight cuboids found
x3mEn
PDA-Benutzer
PDA-Benutzer
 
Posts: 43
Joined: 20.03.2011 22:23

Re: [sub-project] Perfect cuboid

Unread postby fwjmath » 09.09.2017 17:12

EDIT: I was wrong. You never need to check for primes of the form 4k+1, since a diagonal can be written three times as sum of two squares. This reduces the numbers to check down a lot. And the limit you have checked is now beyond 2^32.

-------Original post-------

Hi x3mEn,

In fact, upon reading all the posts (I should really have done this before), I found that the criticism of Robert Gerbicz is correct. Of course it is, he is a really good math experimenter on this front. He is the one who has done power sums.

You are now searching for a perfect cuboid with diagonal g < 2^32, right? Then by triangle inequality, the diagonal of a cuboid is always larger than its sides, therefore, if you found a perfect cuboid, all of its sides would be less than the diagonal, which is less than 2^32. Since all rational cuboid with sides < 2^32 is known (and tabulated), no perfect cuboid was found, we can establish that you will NOT find any perfect cuboid in the search up to 2^32. Am I right?

I think your confidence of your algorithm comes from the fact that you only check for diagonals that are products of primes of the form 4k+1, and you think that there are few. But there are a LOT of them! Most of them will be primes. By the prime number theorem, the density of primes around N is 1/ln(N). For 2^32 it would be 1/32ln(2) > 1/30, meaning that there is a prime in roughly every 30 random numbers. Heuristically, about half of them are of the form 4k+1, which makes 1/60 density. This is huge, because 2^32 is large. Of course, you don't have much to check since they only has a unique decomposition as sum of two squares, but still.

However, if your search extends beyond 2^32, it would be more interesting. The new types of cuboids are also interesting.

But in the end, what we are looking for are perfect cuboids.
Last edited by fwjmath on 09.09.2017 17:35, edited 1 time in total.
fwjmath
PDA-Benutzer
PDA-Benutzer
 
Posts: 56
Joined: 19.10.2010 15:26

PreviousNext

Return to Fehler, Wünsche / Bugs, Wishes

Who is online

Users browsing this forum: No registered users and 2 guests