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 

magicSqr
Hi,
[edit] Just thought of a different way around this, I'll be back... magic² 

29 Nov 2011, 22:34 

typedef
yes


29 Nov 2011, 23:12 

magicSqr
typedef wrote: yes Thanks That's that sorted then, lol 

29 Nov 2011, 23:23 

typedef
Ok. Just those numbers or the list goes on ?


29 Nov 2011, 23:25 

magicSqr
magicSqr wrote: ...so taking the first few we would have these... ad infinitum. 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
But how are you coming up with the numbers ?


29 Nov 2011, 23:57 

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
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
typedef wrote:
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
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 runtime)


30 Nov 2011, 03:29 

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
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
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
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
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
Basically, I mean changing "sumofSqrs[k] = i² + j²" to "bitVector[i² + j²] = 1", where bitVector is bitaddressable (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 32bit 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 8bit 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
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..(b1) ;//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); 

30 Nov 2011, 21:56 

smiddy
I am having enough trouble remembering assembly let alone C. LOL


30 Nov 2011, 23:13 

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, nonzero 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 

Goto page 1, 2 Next < Last Thread  Next Thread > 
Forum Rules:

Copyright © 19992020, Tomasz Grysztar. Also on GitHub, YouTube, Twitter.
Website powered by rwasa.