Please, recommend readers some manual with good opcode reference.
I use the intel books and separate printed versions of the instruction charts are on the wall. :)
1. Flags effected by instructions: EFLAGS Reference. (Volume 1, Appendix A)
2. Instruction Encodings. (Volume 2, Appendix B)

I also have a very nice periodic table of the elements on the wall.

iblis, you are correct - talk is the best we have. :) Have you also thought of sequences like: 7A FF C8 ?? ?? I was also trying to find a method with two Jcc. There seems to be many complex opportunities, but we could systematically rule them out - it would just take time, imo. Also, we should ask the question: in what state must the CPU be in after the five bytes - are we allowed to destroy the stack/registers/etc? Do the bytes have to be contigious in memory? Does execution even have to continue after the five bytes? Not that this will help us on this problem specifically, but there are others.
Posted on 2002-11-21 00:00:01 by bitRAKE

Have you also thought of sequences like: 7A FF C8 ?? ??


Very interesting. But what happens if PF = 0?

[size=12]   If PF == 1       If PF == 0

.----------. .-----------------.
| jpe $+1 | | jpe $+1 |
| / | | / |
| dec eax | | enter ?? ?? ?? |
| ?? ?? | | |
----------' -----------------'[/size]


The PF=0 scenario leads to an enter with 3 bytes of operands and exceeds the 5 byte limit. But I understand your point. There might be some very strange solution out there that normally we couldn't possibly hope to figure out unless we stumbled upon it by accident or brute forced it.





I was also trying to find a method with two Jcc. There seems to be many complex opportunities, but we could systematically rule them out - it would just take time, imo.


I was fiddling with 2 Jccs also awhile back but didn't find anything useful. 2 Jcc's would require 4 bytes unless they overlapped, but all of the Jcc opcodes I see don't allow for overlapping because the opcodes, ranging from 70h - E3h, would jump us out of bounds. (Unless we're allowed to scatter the code - but I don't know if that's allowed. TheSvin could tell you since he invented the question.) You could also maybe overlap one or more of the Jccs with some other opcodes, but it's too late in the day to dedicate my brain to that kind of stress. ;)





Also, we should ask the question: in what state must the CPU be in after the five bytes


Good question. I imagine the post-state can be anything since TheSvin didn't specify. The only state we need is eax/ax = -1. Although with regards to practicality, any stable or correctable state would be preferrable. I think a more important question would be what state should the CPU be in before the five bytes? For example, if the state of the carry flag is always 1, then the problem is solved. ;)
But based on the simplicity of the question, intuition tells me that the pre-state can be anything. We can't rely on any potentially volatile circumstances to be constant.





are we allowed to destroy the stack/registers/etc? Do the bytes have to be contigious in memory? Does execution even have to continue after the five bytes? Not that this will help us on this problem specifically, but there are others.


Again, the person to answer that would be TheSvin, since he invented the question. Although I doubt he gave any thought to any of that when he asked it. I still think that '5' was a typo or a miscalculation on his part. Either that or he was biting off more than he could chew. Getting him to admit to it is another matter. ;)

I personally would like to see it done with 5 contiguous bytes using nothing other than EAX for storage. But in fact that is the scenario that I think is impossible. Having it done another way would still be very impressive to see though. --The best solution? Have a mod edit TheSvin's post and replace the '5' with '6'. :grin:
Posted on 2002-11-21 01:54:56 by iblis
Getting him to admit to it is another matter.

Oh I's no problem, I could admit anything :)
I've proved it before.
The thing is that I don't want to do it right now,
'cause the more I remain silence the more productive stuff I can see from other part in discussion.

Prove me wrong or find solution. That's what I'd say for now.
Despite that the solution hasn't been found, many interesting thought have been shown in discussion about it. So you can call me any name - I still think that discussion is getting more and more usefull for everybody
and I'm not going to finish it :)

You see we just start real analyze here.
We need enumarate all possible short ways to fill reg16 and reg32 with bits.
Give clear sceme on code overlap triks etc. etc.

I didn't say if I had solution or I didn't have it.
But I promisse to say it if you prove that it is impossiple
:)
Prove it! I enjoy the way you think :)
Posted on 2002-11-21 04:45:08 by The Svin
So far I only know of a few operations that can be used to check the status of the parity flag

You forgot of cmovcc option. Might be used with 66 prefix.
Also among other way to set bits there are
stack method (also can be used with 66)
Posted on 2002-11-21 06:09:20 by The Svin
About the CMOV one, I had thought about it but I quickly leaded it out because it doesn't work on Pentiums, and AFAIK you work on a Pentium, so I doubt++ you wanted a CMOV solution. Also, it doesn't seem suitable for <=5 bytes solution, at least at a first analysis.

Stack is cool.. I thought too about some PUSHF tricks (just like the LAHF I mentioned), but in general the 5 bytes requirement make it look tough.
Posted on 2002-11-21 06:18:32 by Maverick

Example:
Question
Is it possible to have a number
(n+1)^2
that have sum of digits = (n-1)/2
It is not possible, my proof is the following code. I have tested all possible solutions to the point where there will never be enough digits in (n+1)^2 to sum to equal (n-1)/2.
   xor ecx, ecx ; (n+1)

sub esp, 16
_0:
mov eax, ecx
mul ecx ; (n+1)^2
mov [esp+4], edx
mov [esp],eax

fild qword [esp]
fbstp [esp]

; sum digits
mov eax, [esp]
mov edx, eax
shr eax, 4
and edx, 0F0F0F0Fh
and eax, 0F0F0F0Fh
imul edx, 01010101h
imul eax, 01010101h
add edx, eax

mov eax, [esp+4]
mov ebx, eax
shr eax, 4
and ebx, 0F0F0F0Fh
and eax, 0F0F0F0Fh
imul ebx, 01010101h
imul eax, 01010101h
add eax, ebx
add eax, edx
shr eax, 24

; compare to (n-1)/2; ECX = (n+1)
lea eax, [eax*2 + 2]
sub eax, ecx
je _x

inc ecx
jns _0
or eax, -1
_x:
add esp, 16
I know it's messy, but it was the least effort. ;)
Posted on 2002-11-21 10:37:49 by bitRAKE
bitRAKE, looks good. I think The Svin wanted a more analytical approach.

Look at the problem this way:

let f(n) = (n+1)^2
and
let g(n) = (n-1)/2

The max number of digits f(n) can be for any given n is: floor( log_10( f(n) ) + 1 )
So the maximum value for the digit sum of any given n is: floor( log_10( f(n) ) + 1 ) * 9

let h(n) = ( log_10( f(n) ) + 1 ) * 9


So to narrow down the amount of whole positive integers you'll need to test, you want to find a value of n such that g(n) > h(n). So to find n you have to write it out as an equality and solve:

(n-1)/2 = ( log_10( (n+1)^2 ) + 1 ) * 9

Instead of doing the math, it's faster to graph it out. If you graph h(n) and g(n) you'll see that g(n) surpases h(n) at approximately n = 74.

So armed with this, and a list of all n's for n < 74, you can prove that it is impossible. ;) And it saves a lot of work and explanation.



This is the kind of method I think TheSvin wanted to try with the "if PF = 1 eax = -1 else ax = -1" challenge. But I don't exactly know how to begin adapting mathematical theory to a 5 byte algorithm. <scratches head>

It's interesting though.
Posted on 2002-11-21 14:56:38 by iblis
iblis, good explaination. That is what I thought in my head - I knew h(n) was logithmic and g(n) linear, and they cross each other at two points. I also knew I'd have to test some values, so I wrote the code. Once (n) is large enough I am done - it is not important to know what the cross over point is imho. My algo is overkill for n=74, but maybe I can use it again. :) I hear that is the difference between engineering and mathematics - in math they want to know the cross over point, in engineering it is okay just to be sure of the answer. For other problems it would be very important not to test more values than needed, but this is not such a case.
Posted on 2002-11-21 15:38:33 by bitRAKE
:)
I like it more and more.
I thank you both iblis and bitRake for getting involved into it.
Now look closely into condition of the problem:
It doesn't tell anything about numeric system.
The only thing is known that it is position numeric system and radix
of it is integer.

Now I'll give you a hint:
Instead of looking for n make radix of numeric system a subject
of your research and you'll find answer very fast.
Posted on 2002-11-21 19:57:42 by The Svin
Svin,
Let's assume the number is in decimal format Then (n+1)^2 can be decomposed as (a+10b+100c+1000d+....)^2 . Likewise (n-1)/2 can be decomposed as (a+10b+100c+1000d+....-2)/2, where a,b,c,d...are the decimal digits. Expanding the first expression gives (a^2+100B^2+10000c^2+1000000d^2+...+(lots of cross products)) . Expanding the second expression gives (a/2+5b+50c+500d+...-1) . Now it can be seen that every digit in the (n+1)^2 expression has a square term, while every digit in the (n-1)/2 expression only has a linear term. Therefore, the first expression will ALWLAYS be greater than the second expression and the second expression has no chance of being equal to the first expression. The same argument holds true for any radix you wish to use. Ratch
Posted on 2002-11-21 21:29:02 by Ratch
Ratch, how can that be true?

n=3

(n+1)^2 = 16

Sum of digits (base 2) = 1

(n-1)/2 = 1 :eek:
------------------------------------------
n=5

(n+1)^2 = 36

Sum of digits (base 2) = 2

(n-1)/2 = 2 :eek:
   xor esi, esi ; (n+1)

_0:
mov eax, esi
mul esi ; (n+1)^2

; count bits in EDX:EAX (base 2)
; this is slow, but fun! :)
or ebx,-1
_1: bsf ecx,eax
btr eax,ecx
inc ebx
jc _1

or eax,-1
_2: bsf ecx,edx
btr edx,ecx
inc eax
jc _2

add eax, ebx

; compare to (n-1)/2; ECX = (n+1)
lea eax, [eax*2 + 2]
sub eax, esi
je _x
_3:
inc esi
jns _0
int3
_x:
invoke _OUTPUT_, esi
jmp _3
Svin, I thought a little about this when I wrote the base 10 code. This is fun - you are a good teacher. You turn like a worm - that is the reason I have explicitly stated the problem again in my own words. I am eager for your surprises! ;)
Posted on 2002-11-21 22:13:55 by bitRAKE
pwnage. :grin:
Posted on 2002-11-21 22:27:36 by iblis
BITrake,
Yes, looks like I did not set up the conditions properly. This problem looks intractable for algebraic equations because the values change in discrete steps. It appears that brute force computing in the way to go for this problem. Sort of like Fermat's Last Thoerem. Ratch
Posted on 2002-11-21 23:49:52 by Ratch
Ratch, I don't think it requires brute force for this problem - my ASM skills are better than my math. :) I will try to work through the math though - I need the practice. Good to see another person join in the discussion.
Posted on 2002-11-21 23:57:56 by bitRAKE
It was very easy task.
Origianl qeustion from my book was harder.
(sum of digits in (n+1)^2=n(n-1)/2)
Now method:
solve equation
(n-1)/2=1
then radix would be
(n+1) and (n+1)^2

since in (n+1) radix system the number would look like
100
and in (n+1)^2 radix system
the number would look like 10
as you can see in both systems sum of digits equal 1.

It was too easy.
To train yourself find number
(n+1)^2 that have sum of digits equal to n(n-1)/2
It's easy since you now know the way.
Posted on 2002-11-22 00:25:59 by The Svin
Sort of like Fermat's Last Thoerem

What do you mean by " Fermat's Last Thoerem"?
Might be "Fermat's Big Theorem"?
It was proved using analitic geometry (trough curves of 3rd d. - elipsoids)
and the proof has nothing to do with brute force in computers.
Posted on 2002-11-22 00:45:26 by The Svin
Svin,
You are right about FLT not needing a computer. I was thinking of the 4 color map problem proof which did rely on copious amounts of computer resources. See http://www.pbs.org/wgbh/nova/proof/ for what I mean by FLT. Ratch
Posted on 2002-11-22 01:24:10 by Ratch
I read the artical before.
But we in Russia call it Big Theorem or Major Theorem,
to differ it from Minor Theorem.
I don't know why it called Last in the West.
How do you call Minor Theorem?

As to interview, from practical point of view it's uselles.
To understand Wiles proof one should read first Utaka Taniyama. Then Wiles proof that is based on it. ~ 250 pages of reading.
And very few people can understand it.
Posted on 2002-11-22 02:25:04 by The Svin
Svin,
Well, the rest of the world calls it FLT, because it was his last theorem. I don't know what the rest of the world calls the Minor Thoerem. If fact, I don't know what the Minor Theorem is, because I am not a mathematician, or familiar with Fermat's work on number theory. Ratch
Posted on 2002-11-22 10:55:29 by Ratch
I have heard it called both. I don't think FLT is exclusively a western term, nor is FBT exclusively a non-western term.

IIRC the theorem says a^n + b^n = c^n is impossible to solve for non-zero integer values and n > 2.

I don't see what this has to do with '(n-1)/2 = sumdigits((n+1)^2)' though. :confused:
Posted on 2002-11-22 11:38:55 by iblis