flat assembler
Message board for the users of flat assembler. Index > Main > can an algorithm be made for this? Goto page 1, 2  Next
Author
 Thread  magicSqr

Joined: 27 Aug 2011
Posts: 105
magicSqr
Hi,

 Just thought of a different way around this, I'll be back...

magic² 29 Nov 2011, 22:34  magicSqr

Joined: 27 Aug 2011
Posts: 105
magicSqr
I was looking for a way to generate, in numerical order, integers that are the sum of two distinct squares, so taking the first few we would have these

5 = 1 + 4
10 = 1 + 9
13 = 4 + 9
17 = 1 + 16
20 = 4 + 16
25 = 9 + 16
26 = 1 + 25
29 = 4 + 25

Is there any way I can generate these in order?

thanks

magic² 29 Nov 2011, 22:47  typedef

Joined: 25 Jul 2010
Posts: 2908
Location: 0x77760000
typedef
yes 29 Nov 2011, 23:12  magicSqr

Joined: 27 Aug 2011
Posts: 105
magicSqr
typedef wrote:
yes

Thanks That's that sorted then, lol 29 Nov 2011, 23:23  typedef

Joined: 25 Jul 2010
Posts: 2908
Location: 0x77760000
typedef
Ok. Just those numbers or the list goes on ? 29 Nov 2011, 23:25  magicSqr

Joined: 27 Aug 2011
Posts: 105
magicSqr
magicSqr wrote:
...so taking the first few we would have these...

I'll be using GMP as the numbers get bigger, but that's not the problem, it's the general algo I'm struggling with as there isn't really an order to the squares i.e the next few

34 = 9 + 25
37 = 1 + 36
40 = 4 + 36
41 = 16 + 25
45 = 9 + 36

magic² 29 Nov 2011, 23:41  typedef

Joined: 25 Jul 2010
Posts: 2908
Location: 0x77760000
typedef
But how are you coming up with the numbers ? 29 Nov 2011, 23:57  typedef

Joined: 25 Jul 2010
Posts: 2908
Location: 0x77760000
typedef
If you are just putting down random #s then it will be even harder to come up with an equation.

I was designing one based on those numbers, but I can't really go anywhere if I don't know how the numbers came about.

The first thing I noted is that the numbers to the right are Squares. So for that,

Let : X >= 2
Let : S = (X*X) // Square

Again, I don't know how the #s came about (If you just dreamed of them or something)

Then

if ( X AND 01 ) == ODD
else
EVEN

If that even helps

But first tell me how you are getting the numbers. 30 Nov 2011, 00:04  magicSqr

Joined: 27 Aug 2011
Posts: 105
magicSqr
Not sure I understand the question typedef ¿

Each number in the list so far (5, 10, 13, 17, 20 .....) can be expressed as the sum of two distinct squares (i.e. different i.e. 8 = 2² + 2² no good and I'm not including 0 as a square so 16 = 0² + 4² also no good)

I'm not sure how else to explain it 6 = 1 + 5 not two squares
6 = 2 + 4 not two squares
6 = 3 + 3 not two squares

hence 6 is not in the list

magic² 30 Nov 2011, 00:10  magicSqr

Joined: 27 Aug 2011
Posts: 105
magicSqr
typedef wrote:

The first thing I noted is that the numbers to the right are Squares. So for that,

my OP

magicSqr wrote:
integers that are the sum of two distinct squares...

that's exactly where the numbers are coming from

1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 14, 15, 16 can't be expressed (in integers) as the sum of two distinct squares

num = a² + b² (where a > b > 0) 30 Nov 2011, 00:22  LocoDelAssembly

Joined: 06 May 2005
Posts: 4624
Location: Argentina
LocoDelAssembly
https://oeis.org/A004431 <- This is what magicSqr is trying to get (i.e. generate the first N terms of the series with N known at run-time) 30 Nov 2011, 03:29  magicSqr

Joined: 27 Aug 2011
Posts: 105
magicSqr
Thanks LocoDel That was roughly how I was going to explain it in my OP but thought the other way was easier to understand.

The numbers in the list of integers that are the sum of two distinct squares are made up like this:

1) The number must have at least one prime factor of the form (4k+1)
2) If the number has any prime factors of the form (4k+3) then the exponent of this factor must be even.
3) The number can have 2 raised to any power >= 0 as a factor.

so we would have (2^3)*(5^1)*(7^2) = 1960 = 14² + 42²

but (2^3)*(5^1)*(7^1) = 280 cannot be expressed as the sum of two distinct squares because 7 is of the form (4k+3) and is raised to an odd power.

The reason I was thinking the other way is easier is that the above requires extensive testing whereas, when we know we want numbers that are the sum of two distinct squares, why not just generate them.

One of the methods mentioned in your link actually generates Pythagorean primitive triples

a² + b² = c²

not a² + b² = c

One way I could achieve what I'm after (in BASICish terms)

k=1
for i = 1 to (n - 1)
for j = (i + 1) to n
sumofSqrs[k] = i² + j²
k = k + 1
next j
next i

and then sort the array 'sumofSqrs' into numerical order, but this seems a long way round as well. 30 Nov 2011, 12:47  smiddy

Joined: 31 Oct 2004
Posts: 557
smiddy
Can you generate the sum of the two squares, to n, then sort on the answer in a runtime created array, with tracking of each component making up the sum?

Try working the long way first, then optimize for elegance and speed second?!

I am typing this on my phone, so example code would take forever to fat finger. LOL 30 Nov 2011, 13:09  magicSqr

Joined: 27 Aug 2011
Posts: 105
magicSqr
or create seperate arrays for each 'i' then interleave the results at the end, knowing that each seperate array is already in numerical order. hmmm, might just take a look into that. 30 Nov 2011, 13:22  LocoDelAssembly

Joined: 06 May 2005
Posts: 4624
Location: Argentina
LocoDelAssembly
Do you have an estimate of how much the terms are separated from each other with n large? Because if they are as near as the example at OEIS, you should consider testing with a single bit map and then printing the number by scanning for 1s in the bitmap. In this method, N could be defined as the bitmap size, and then your algo would try to fit as much numbers as it can before running out of space.

I could provide you the code for this, but I'll let you attempt this by yourself first. 30 Nov 2011, 15:47  magicSqr

Joined: 27 Aug 2011
Posts: 105
magicSqr
Thanks Loco,

I'll take a look at the density for large n and let you know. Not sure I follow the second part of your post but I'll give it a go and see where I get magic² 30 Nov 2011, 15:57  LocoDelAssembly

Joined: 06 May 2005
Posts: 4624
Location: Argentina
LocoDelAssembly
Basically, I mean changing "sumofSqrs[k] = i² + j²" to "bitVector[i² + j²] = 1", where bitVector is bit-addressable (i.e. you use BTS instruction). Later, rather than sorting you just walk the entire array printing all the indexes where you find a bit set to 1.

This method should be more efficient than storing numbers as 32-bit numbers (or bigger numbers if you want to get a really long list), but if the series looses density as N gets large then perhaps the space wasted to store zeroes becomes too costly to be useable. Other option could be storing the difference with the previous number, but you'll probably need several lists like you mentioned earlier to do this to avoid costly insertions. *

*The list I mention is this: [5, 5, 3, 4, 3] which would represent [5, 10, 13, 17, 20], but the former could probably use 8-bit numbers or perhaps even fewer bits, that depends on the maximum spacing (although you could always reserve a few magic numbers to tell the code that the next, say, dword is a number rather than just a difference with the previous term). 30 Nov 2011, 17:01  cod3b453

Joined: 25 Aug 2004
Posts: 618
cod3b453
Apologies for using C on this; tried to make it easy to convert. Note that I haven't confirmed this is either correct or particularly optimal. (It currently takes minutes to scan all pairs whose squares sum to less than 2^20 but there is no storage requirement other than registers)

The method basically increments a modulus* (m) to match with parameters a,b which you can visualise as columns (b) and rows (a) in a matrix. Since a =/= b we can discount one triangle, the diagonal and the first column of the matrix.

*m can be considered the square of the hypotenuse of a triangle so that it can be compared with a*a + b*b and avoid the need to sqrt.
Code:
``` ;//for (m = 5; m; m = m + 1)
m = 5;
do
{
;// let col = 1..floor(sqrt(m))
;//for (b = 1, bb = (b + 1) * (b + 1); bb < m ; b = b + 1, bb = (b + 1) * (b + 1))
b = 1;
bb = 4;
do
{
;// let row = 0..(b-1)
;//for (a = 0; (a < b) && (bb < m); a = a + 1)
a = 0;
do
{
;// convert row to index and square
aa = (a + 1) * (a + 1);

;// calculate sum
r = aa + bb;

;// if target modulus hit, record and increment
if (r == m)
{
;//printf("%08X %04X %04X\n",r,(b+1),(a+1));
m++; ;// restart loops required???
}

a = a + 1;
}
while ( (a < b) && (bb < m) );

b = b + 1;
bb = (b + 1) * (b + 1);
}
while (bb < m);

m = m + 1;
}
while(m);    ```
If anyone can spot any holes let me know  30 Nov 2011, 21:56  smiddy

Joined: 31 Oct 2004
Posts: 557
smiddy
I am having enough trouble remembering assembly let alone C. LOL 30 Nov 2011, 23:13  magicSqr

Joined: 27 Aug 2011
Posts: 105
magicSqr
smiddy wrote:
I am having enough trouble remembering assembly let alone C. LOL

ROFL, and pseudo C++Basic is even scarier. I'll plough my way through although me thinks the algo may be missing the point but not sure yet.

for LocoDel,:

it 'appears' the density for n = a² + b² may be limiting around n/5.
The first few thousand are higher but as I get into tens of millions there seems very little fluctuation from ~ 20%. The highest difference I have found between successive terms is 56, although this will probably grow higher for larger n. It seems that a byte would still be big enough for very large n though.

Further to what I am working on, I would require n to be the sum of two squares in *at least* four different ways.

In the prime factorization of n, as stated earlier, it can have factors of the form {4k+3) only if these are raised to an even power. n can also have 2 raised to any power >=0 as a factor.
If n satisfies these conditions and has at least one prime factor of the form (4k+1), it can be expressed as the sum of two, distinct, non-zero squares.
The number of ways a particular n can be expressed this way is *totally* dependent on the prime factors of form (4k+1).

For n to be expressible as the sum of two squares in *at least* four ways, the *minimum* requirements are that it has any of the following combinations of these type of prime factors (4k+1)...{LaTeX would be handy here, any way of incorporating it Tomasz?)

n = p1^7 or greater exponent
n = p1^1 * p2^3
n = p1^2 * p2^2
n = p1^1 * p2^1 * p3^1

The fourth example actually covers the lowest n that is of the required type

1105 = 5 * 13 * 17 = (4*1 + 1)(4*3 + 1)(4*4 + 1)

and

1105 = 4² + 33²
1105 = 9² + 32²
1105 = 12² + 31²
1105 = 23² + 24²

Forgive me for waffling, I'm a great 'doer' but an awful teacher magic² 01 Dec 2011, 00:04  Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First  Jump to: Select a forum Official----------------AssemblyPeripheria General----------------MainTutorials and ExamplesDOSWindowsLinuxUnixMenuetOS Specific----------------MacroinstructionsOS ConstructionIDE DevelopmentProjects and IdeasNon-x86 architecturesHigh Level LanguagesProgramming Language DesignCompiler Internals Other----------------FeedbackHeapTest Area
Goto page 1, 2  Next

Forum Rules:
 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot vote in polls in this forumYou cannot attach files in this forumYou can download files in this forum