Rechenkraft.net e.V.

die erste Adresse für Distributed Computing
Unterstütze Rechenkraft.net e.V.
Mit Suchkraft hier suchen:
 
It is currently 22.11.14 15:00

All times are UTC + 1 hour [ DST ]




Post new topic Reply to topic  [ 56 posts ]  Go to page Previous  1, 2, 3, 4, 5
Author Message
Unread postPosted: 31.03.11 12:36 
Offline
PDA-Benutzer
PDA-Benutzer

Joined: 20.03.11 22:23
Posts: 39
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.


Top
 Profile  
 
Unread postPosted: 31.03.11 15:47 
Offline
PDA-Benutzer
PDA-Benutzer

Joined: 08.06.10 19:06
Posts: 56
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?


Top
 Profile  
 
Unread postPosted: 01.04.11 18:46 
Offline
PDA-Benutzer
PDA-Benutzer

Joined: 20.03.11 22:23
Posts: 39
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 51 times
Top
 Profile  
 
Unread postPosted: 08.04.11 13:59 
Offline
PDA-Benutzer
PDA-Benutzer

Joined: 20.03.11 22:23
Posts: 39
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?


Top
 Profile  
 
Unread postPosted: 02.12.11 15:47 
Offline
Taschenrechner
Taschenrechner

Joined: 14.04.10 08:32
Posts: 11
Is there any progress? :roll:

_________________
Image


Top
 Profile  
 
Unread postPosted: 26.03.12 22:16 
Offline
Fingerzähler
Fingerzähler

Joined: 26.03.12 22:13
Posts: 1
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


Top
 Profile  
 
Unread postPosted: 06.04.12 23:46 
Offline
PDA-Benutzer
PDA-Benutzer

Joined: 19.10.10 15:26
Posts: 52
@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.


Top
 Profile  
 
Unread postPosted: 16.09.12 19:18 
Offline
PDA-Benutzer
PDA-Benutzer

Joined: 20.03.11 22:23
Posts: 39
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


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 56 posts ]  Go to page Previous  1, 2, 3, 4, 5

All times are UTC + 1 hour [ DST ]


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group