Coding Challenges

[Hooman]

I told you people would want to kill me for that one.  

Consider this.

Code: [Select]

j = i = 5;

Here, i = 5 is an expression that evaluates to 5. Essentially, = is an operator with a side effect of assignment. Same idea with either ++i or i++. They are both operators with a side effect of assignment. Now consider:

Code: [Select]

i = i++ + ++ i;

You have 3 operators here, and according to that paragraph I quoted, when evaluating the expression (remember that the whole line is an expression that evaluates to the result getting assigned to i on the left) the order of the side effects of those 3 operators is undefined.

(There was some discussion in a compiler course I took on what that expression did. People came to the conclusion that it was undefined. Or maybe it was j = i++ + ++i; ?)

Here's another one for you:

Code: [Select]

i = 0;
j = i++ + i++ + i++;

What is the value of j? I just tried this with MSVC. When I tried it, I got 0.
Now try this:

Code: [Select]

i = 0;
j = ++i + ++i + ++i;

What is the value of j? I just tried this with MSVC, and I got 7. How does that work? So I took a look at the compiled code and here is what it did.

It incremented the value of i, and then stored it. (++i + ++i + ++i).
Then it read i from memory and incremented it again. (++i + ++i + ++i).
Then it read i from memory, and added it to i from memory. (++i + ++i + ++i).
Then it read i from memory and incremented it again. (++i + ++i + ++i).
Then it added that value to the sum of the previous 2. (++i + ++i + ++i).
Then it performed the assignment to j.

Note how the effect of the first ++i was felt by the second ++i. Then the effect of both the ++i was felt by the third ++i. Ok, so this seems to follow exactly the method you've described so far. But is that surprising? No. MSVC obviously follows a particular method here. This seems to be the most obvious way of doing things, so no real surprise they've done it this way.


Ok, so now try:

Code: [Select]

i = 0;
j = i++ + ++i + ++i;

The result is 4. Try doing this one in a left to right order with ++ (pre or post) taking prescendence over +. You should get 5. Ok, now don't increment the i++ (post) until after j is assigned. You get 3. Ok, so now evaluate ++i, and then add that to i++, and then add the third term ++i. And then finish the increment from the ++i. You get 4. Go look at the assembly. This was the order in which is was done. It's not quite so obvious how that follows your set of rules now. The ++i on the RIGHT side of the first + took precendence over the i++ on the LEFT side of it. Clearly not left to right ordering here. It's also not right to left ordering, since that would give you 6.

Ok, now we try:

Code: [Select]

i = 0;
j = ++i + i++ + ++i;

The result is again 4. Taking a look at the assembly, the ++i on the LEFT is evaluated first. Then the i++ is evaluated (remember, it evaluates to the value before the increment) and added to that result. Then the final ++i is evaluated. The result is assigned to j. And then finally, the effect of i++ is done. Ok, so in this case, it was left to right ordering. Or was it? It could equally well have been right to left ordering here and you'd get the same result. Not really any way to tell here.

Next up:

Code: [Select]

i = 0;
j = i++ + i++ + ++i;

The result is 1. In this case, the (i++ + i++) was performed first. Simple left to right ordering in this case.

Code: [Select]

j = ++i++;

Produces a compile error. "needs l-value". As does

Code: [Select]

j = ++(i++);

(Not too surprising)

Code: [Select]

j = (++i)++;

Results in 1.


Also, interestingly enough.

Code: [Select]

i = 0;
j = (++i + ++i) + ++i;

Evaluates to 7.

Code: [Select]

i = 0;
j = ++i + (++i + ++i);

Evaluates to 9.
Does that last part bother anyone else here? On closer inspection, the 3 increments are performed before any of the additions on that last example. I guess I can understand that.


As a final set of examples:

Code: [Select]

i = 0;
j = ++i = ++i + ++i;
i = 0;
j = ++i = (++i + ++i);
i = 0;
j = (++i = ++i) + ++i;

The results are 6, 6, and 6. (But the values of i are 6, 6 and 3).


So yeah, MSVC has probably followed a certain standard (even if the C++ specs don't specify one here). It doesn't mean one particular compiler is going to produce undefined results. Of course it won't. Not unless it's using random numbers during the compilation process. (I'm sure that would bother most people). But it does mean that a different compiler (that follows the C++ specs) CAN produce different results for the same code. It doesn't mean it will, especially not if there is an obvious way of doing things. But as for the standard that MSVC uses, the best I can determine is the following. The ++i's take effect on the i in a left to right order, and if an expression can be evaluated in a left to right order following the precendence rules, then it is. Otherwise, the ++i's will continue taking effect and the expressions are evaluated afterwards. The assignments seem to take place after the ++i's, and then the i++'s seem to take effect after the assignments.

Ay any rate, I don't buy your simple left to right ordering theory. Not without extra rules to clear up some issues. Nor do I trust any expressions where a variable is used more than once on the same line involving ++ (pre), ++ (post) or =.

[LupusShearhart]

Well - in theory, it's undefined, but that's merely theory. I thought coding was s'pposed to be applied/practical applications? *shrug* Oh well, no harm done.

'sides, the only way I'd want to kill ya is if you completely destroyed everything that is Outpost... so... :-P

[Hooman]

'sides, the only way I'd want to kill ya is if you completely destroyed everything that is Outpost... so... :-P

Lol. Well, good to know.  :rolleyes:

But as for how every compiler that I've ever seen does it, you 3 people all provided correct answers. Although, I heard from Eddy earlier today that one of my examples from my last post gave a different answer in Tubro C than it did in MSVC.  :lol:  I'd be curious to know a little more about this.


Btw, there are currently only 2 unsolved challenges left. I think they were #4 and #11? (The one about making the compiler calculate constants for you, and the "improved"/harder version of #1). Would people like some more challenges to be posted?    (I'll avoid the "undefined" answers from now on I think).
 

[Eddy-B]

okay, since you really like code with NO jumps/branches.. try this one:
create a string -> HEX converter routine without using branches

example:
input = "2A"  (i.e. 0x32 0x41)
output = 0x2A

a 2 digit converter is enough, since a 4 digit string simply uses the routine twice etc..

have fun!

PS: as an added 'difficulty' it should be able to accept uppercase and/or lowercase chars, so an inut of "2a" should also give a correct answer.

[Hooman]

Ohh, I like it. I'll try it out after I get some school work done.  <_<

Does it matter what happens if a non hex string is given? Undefined output? Just plain doesn't crash? Zero output?
 

[Eddy-B]

oh, 1 extra challenge: it should be able to handle 1-digit inputs as well (in that case the 2nd "digit" is the terminating zero).

It is okay if a non-hex string gives undetermined output.

[Hooman]

Here you go Eddy. Here is some sample code where two hex digits from a string are converted to an int. (I could have used char, but the original code used cout and it displayed the character rather than the value. I also decided not to assume anything about the calling convention and let the compiler handle loading parameters and retruning the return value.)

If a NULL string pointer is passed in, it should crash, but otherwise it shouldn't. At worst, it should return garbage results if the input wasn't in the proper range. I added some checking for both the first and second characters being NULL. I also made sure that if only a single digit is passed in (before the NULL terminator), it'll return the number in the ones-place, and not in the sixteens place. Not sure if that's what you wanted, but it seemed to be the most useful way of coding it. Although, not correcting this would have made for smaller code, as would not caring if the first character was a NULL or not and reading the second one anyways. I checked against this to avoid memory access errors.

Code: [Select]

#include "stdio.h"


// "0" 48 (0x30) 00110000  -  "9" 57  (0x39) 00111001
// "A" 65 (0x41) 01000001  -  "Z" 90  (0x5A) 01011010  -  "F" 70  (0x46) 01000110
// "a" 97 (0x61) 01100001  -  "z" 122 (0x7A) 01111010  -  "f" 102 (0x66) 01100110


int HexConvert(char *hexString)
{
	int retValue;

	__asm 
	{
  // Load the string address
  MOV EDX, hexString
  XOR EAX, EAX    // Clear return value to 0

  // Convert the first digit
  MOV AL, [EDX]    // Load the character
  // Convert letters to 10+
  MOV CL, AL
  SHL CL, 1
  SAR CL, 8
  SUB AL, CL
  SHL CL, 3
  SUB AL, CL
  // Cut off non numeric bits
  AND AL, 0x0F
  // At this point in AL, numebrs 0-9 should produce 0-9 and letters A-F and a-f should produce 10-15.


  // Process a second digit (if the first wasn't a null terminator)
  MOV CL, [EDX]    // Load the character
  CMP CL, 0
  SETNE CL
  MOVSX ECX, CL
  ADD EDX, ECX
  SHL EAX, 12    	// Store previous result in upper nibble of AH

  // Convert the first digit
  MOV AL, [EDX]    // Load the character
  // Convert letters to 10+
  MOV CL, AL
  SHL CL, 1
  SAR CL, 8
  SUB AL, CL
  SHL CL, 3
  SUB AL, CL
  // Cut off non numeric bits
  AND AL, 0x0F
  // At this point in AL, numebrs 0-9 should produce 0-9 and letters A-F and a-f should produce 10-15.

  // Ignore result if terminating NULL and use a single digit
  MOV CL, [EDX]    // Load the character
  CMP CL, 0
  SETE CL
  SHL CL, 2
  SHR EAX, CL    	// (If CL == 0) Move upper nibble of AH to lower nibble, lower nibble of AL is 0


  // Combine nibblein AH with nibble in AL
  OR AL, AH    	// Value is now in AL
  XOR AH, AH    	// Clear AH
  MOV retValue, EAX
	}

	return retValue;
}

void main()
{
	char *text = "2A";
	printf("%X\n", HexConvert(text));
}

[Eddy-B]

i'll proof-read ur code during my lunch break.
As for the "what i wanted":

input="2A" -> output = 0x2A
input="A\0" -> output = 0x0A  (1 digit with terminating NULL)

the first digit cannot be NULL, since you'd have an empty string that way!
if you DO input "\0A" i think my routine may even still produce 0x0A as an output, but i'd have to check that

btw: my routine is 14 lines of asm (not counting the push and pops to save registers, sice you also do not save them, nor the RET). Anyway: see if you can scrape off some bytes.
Oh, and i written it in asm altogether, not in C - but that shouldn't matter..

[edit] It seemed i was too soon with that reply :blush: the check for 1 digit i did in my main, and does use a branch, so that part is excluded from the 14 lines, but i'll work it in

[Hooman]

Ahh yes, I thought that check was a little odd to put into asm without branches. If it was just converting a single byte to it's hex equivalent (1 nibble), the core of what I wrote was only about 8 lines I think. My checks for things like 0 terminators and whatnot infalted it quite a bit. Still, I'm sure there was room for improvement before that anyways. I'll take another look sometime later on.
 

[Eddy-B]

I worked out the 1-digit check (branch free), adding 10 lines of asm code. I did find some odd compiling from MSVC btw: my asm compiles to a much smaller code using Turbo C..

btw: SAR CL, 8  is illegal by itself, and is translated into 8 time SAR CL,1
---------------

to extend to this challenge (the original idea for this).. i created a com-executable that accepts a 1 or 2-digit HEX input (from the command line) and sets the screen mode to whatever you supply. The code on its own is 78 bytes, and i've added another 80 bytes of "usage" text, to make a total of 160 bytes MODE.COM
---------------

my coding challenge #2:
I got a nice little homework assignment a dozen years ago: create a multiplication "program", that accepts two 8bit arguments, and of course a 16bit product. I think we discussed something like this before.  The original question i got was to do it in Z80 language, but it would work best in 8086 for now.
It has to be fast, and short; jumps/branches are allowed, but no advanced opcodes, and do not use MUL. Factors are supplied in AL and DL (default for __fastcall) and are signed. Resulting product should be returned in AX.

Code: [Select]

short Multiply(char factor1,char factor2)

challenge #3:
same thing, but a division: it takes a 8bit divisor in AL and 8bit divider DL. The result: quotient is an 8bit "integer" in AL and an 8bit remainder (uhm.. well, just put it in AH for now). Again all of those are signed.

Code: [Select]

short Divide(char divisor,char divider)

Example: 11/5 = 2, remainder 1  =>  

Code: [Select]

short result=Divide(11,5);
char quotient=result & 0x00FF;
char remainder=result >> 8;

It doesn't matter much - it's just a way of communicating back to c.
Raw code for both challenges to be written as an *.asm source file, using basic 8086 instructions (no DIV and MUL).

Any of the other people who know a little about coding wanna give it a shot ? (coz i know hooman can do this - it's no big deal for hm)

[Hooman]

Ahh yes. I think I there is a post around here somewhere with the Z80 solution for multiplication. I think I'll leave this one for other people.

I'm gonna go look into that SAR thingy. That's not something I noticed.  :blink:



Edit: I get a 3 byte opcode for SAR CL, 8. No problems there for me.
 

[Eddy-B]

Must be a new Pentium code then. All i know is shifts and rotates etc are only 1 bit at a time, i.e. SHL AX,1  and when u want to shift more (upto 256 positions) you should use CL as an index:  MOV CL,8   SAR AX,CL

then again, i never got around to learning the new instruction set of the pentium. It seems both win32-based borland and MS compilers compile it to that opcode. It's just that i like to use my DOS-based compiler for small code, as it tends to create much smaller code

[Hooman]

Ahh yes, I remember some comment about not being able to shift by more than one bit on older machines unless the number of bits to shift by was stored in CL. Now though, I just write the code and see if the assembly complains. They've done a fair bit of work since the pentium to make the instruction set more orthogonal. Now, if it seems like you might be able to do it, you usually can. Although, if you check the actual encoding of the opcodes, that might vary more than you expected since you're using new added on instructions.

I'll get back to cleaning up that code as soon as a finish an assignment for school. Gah, I hate compositions, they take me so very long.  :angry:  

[Eddy-B]

So... ?
anyone want to give it a try?

[Hooman]

Not too sure what you're referring to.

Anyways, drowning in school work. Will get back to this in... a month?   Ok, not quite that long. I've largely forgotten about cleaning up that code, and I don't have time for it at the moment.

There are still 4 unanswered challenges by my last count.


There was that one about outputting your own source code without modifying any variables you defined.

There was one about getting the compiler to calculate constants for you. Feel free to use compiler specific extensions to fine tune this one and get it working right. I've heard some compilers are more fussy about compile time, and other are more fussy about optimizing.

There are two from Eddy. One about multiplying and one about dividing.


Did I miss any? Or do you not feel that hex converted is really answered? (I know it could be better).

[Eddy-B]

the hex-convert is ok. was just for fun anywayz.
The multiply & divide: use your preschool math abilities  (1 word: long-division ,, or are that 2 words?)

[Hooman]

Well, it seems nobody was planning on answering the most recent question about a program that outputs it's own source code. (Without modifying any variables you have access to. That is, any memory that is written, is done so deep within standard C functions that you can't see and don't have access to, such as printf or cout).


Well, I was cleaning up my harddrive and deleting old C++ projects. I thought I'd post this code before deleting it.

Code: [Select]

#include <stdio.h>

void main()
{
char *escape = "\\"; char *enter = "\n"; char *quote = "\"";
char *string = "#include <stdio.h>%s%svoid main()%s{%schar *escape = %s%s%s%s; char *enter = %s%sn%s; char *quote = %s%s%s%s;%schar *string = %s%s%s;%sprintf(string, enter, enter, enter, enter, quote, escape, escape, quote, quote, escape, quote, quote, escape, quote, quote, enter, quote, string, quote, enter, enter, enter);%s}%s";
printf(string, enter, enter, enter, enter, quote, escape, escape, quote, quote, escape, quote, quote, escape, quote, quote, enter, quote, string, quote, enter, enter, enter);
}

I know it looks a little sick, but it works. Every variables I defined remains constant. The only memory writing should occur deep within printf to variables I have no control ot access to.
 

[BlackBox]

The only memory writing should occur deep within printf to variables I have no control ot access to.

Just to be picky since it would be fun

You (well, the compiler) still has to write memory on the stack in order to push parameters to printf()!

i.e

Code: [Select]

push ...
push ...
.. etc for all other parameters ..
call _printf

And of course, the call will modify the stack itself (storing the return address).

Not to mention there will be plenty of register modifications (if you wanted to be picky a register is a form of 'memory' albeit inside the CPU). But yes, I assume you meant real RAM; pushing stuff to the stack would write the memory

Not to sound harsh but to sound picky for fun's sake

[Hooman]

Lol!

Alright, fine be picky. Run it on a SPARC.

(It usues the register wheel to pass parameters).



Besides, the fact that the compiler might insert instructions to puss stuff on the stack, is pretty much equivalent to printf modifying memory deep within. You have no control over it, and can't make it do anything special. Such as a cheap hack way to increment a variable. Besides, if I said function like printf are allowed to modify memory, I guess I'm sorta implying that you can actually call printf. Besides, that memory is only being modified by the call to printf. If you dno't call printf, that wouldn't happen.



 

[Hooman]

Well why not add a few new challenges.  B)


#12.
Suppose b is a fixed odd integer, and suppose c is some multiple of b.
(Treat b as a constant, and c as a variable).
We want to compute c/b.
That is, we want to divide by an odd constant b, where we know beforehand the remainder after division will be 0.
Do this (for arbitrary odd b ) in a way that is likely faster than using a division instruction.


Bonus: Do this so it is correct whether we are using signed or unsigned integers.

Super Bonus: Extend this method to the case where b is even.
(This may require additional instructions to compute. But it should still be done with fast instructions so that it is still likely a gain on many computers.)



Ex:
A simple case: Let b = -1. Then c/b = c*b.
On most computers multiplication will be faster than division. Hence this would be an acceptable solution.

[Hooman]

#13 Base Converter
Write a converter to express numbers in a different base b.
For each base b, make the following output:
A. A table listing the representations in base b of the numbers from 0 to 15.
B. A table listing the usual representation of numbers for the first 16 encodings of base b numbers. (Sorta like the reverse of table A).

Challenge: Do this for the following bases:
I. b = -2
II. b = -1 + i (where i = sqrt(-1))


Note: Both systems are expressible in binary. (i.e., the with the digits 0 and 1).


Have fun.  :lol:

[jwhiteheadcc]

#13 Base Converter
Write a converter to express numbers in a different base b.
For each base b, make the following output:
A. A table listing the representations in base b of the numbers from 0 to 15.
B. A table listing the usual representation of numbers for the first 16 encodings of base b numbers. (Sorta like the reverse of table A).

Challenge: Do this for the following bases:
I. b = -2
II. b = -1 + i (where i = sqrt(-1))


Note: Both systems are expressible in binary. (i.e., the with the digits 0 and 1).


Have fun.  :lol:

#13 isn't so bad...  Hint:  Instead of say 1,10,100,1000... you'de have -1,10,-100,1000... and thus some negative decimal numbers become positive in base -10 and also the other way around.
I won't show the even simpler way for binary numbers to/from -2 base because I want others to find it!  


For the complex number, you just do the same but use a coordinate pair such as (3,4) in (x,y) coordinate form.
The radius of the base is 5 and the angle is the arctangent of 4/3rds.
Create an inverse function to go both ways.  

Now to win his challenge, you'll have to create an actual program that achieves that for both (-2,0) and (-1,1).  <--- note that the negative can be considered 2 at an angle of 180 degrees.


GL Ya'll!
 (thumbsup)

[Hooman]

I would just like to repeat myself on something.

Note: Both systems are expressible in binary. (i.e., the with the digits 0 and 1).

That is, in each system, you can express all the numbers as a bit vector, where each bit corresponds to powers of the base. The base -2 case is easy to see, but not so much for the other one.

Ex: (base -1 + i)
b_(n-1) (-1 + i)^(n-1) + ... + b_1 (-1 + i)^1 + b_0 (-1 + i)^0
where each of the b_i's is either 0 or 1.

So the bit strings would be as follows:
00: 0 * (-1 + i) + 0 * (1) = 0
01: 0 * (-1 + i) + 1 * (1) = 1
10: 1 * (-1 + i) + 0 * (1) = -1 + i
11: 1 * (-1 + i) + 1 * (1) = i
...


Really though, some justification should be provided as to why every number can be expressed where each b_i is either 0 or 1.


Btw, if you know how to solve it, just solve it. Don't wait for other people.
 

[jwhiteheadcc]

<in reply to PM> I didn't see that you meant for 1/b to be a constant.  This should have been obvious even as tired as I was.

If 1/b=p/q then we can set q to a power of a common base.
For example, if 1/b=0.00123456 then p=1.23456 and q=10^-3, if using scientific notation.
Multiplying an integer using q=power of 2 is also possible.
Notice that I said nothing about rather b is odd since being even is just going to shift q to the left.  Normally you don't store q, but instead it's power.  This is called floating point.   :heh:

c/b is then c*p/q=c*p shifted to the left (or right) by the log_2 of q.
If q=2^n, then c/b=(c*p) << n.

Since i and -1 are both integers, then it's realitively easy to just say that if I have a coordinate system (x,y), that I can map it to (x',y').

For example, to display -5 in base i-1:
1)  We first convert -5 to binary and get -101.
2)  We find the mapping for (x,y) <-> (x',y').
(x',y') is i-1 for one's place in -101.
(x,y) is 1 for one's place in -101.
It seems that mapping is (x',y')=x(i-1)=xi-x and (x,y)=(x',y')/(i-1).
3)  -101 becomes (100+00-1,-100+00-1)=(11,-101)=11 - 101i.

Solving this for a base of -2 seems a lot easier.  

[Hooman]

I'm not sure I fully understand what you're trying to say there, so bear with me if I get this wrong.

My first concern with your answer is precision. If you're using floating point, then there is a certain precision required to ensure the resulting answer is correct. It's certainly possible that the floating point registers on the CPU you're using provide enough precision that any integer will end up being correct (after rounding).

1/b=0.00123456 then p=1.23456 and q=10^-3

Note that this is subject to rounding errors. The value of 1/b might not be expressible in such an easy format. Think about repeating decimals, or ones that are long enough to overflow the precision of the registers. Try expression 1/3 in binary for example.
1/3 = 1/4 + 1/16 + 1/64 + 1/256 + 1/1024 + 1/4096 + ...

It takes quite a few bits actually.

I guess I'd need a bit of insurance that the result will be correct with rounded values. You could show this by giving maximum error bounds for your method and show what precision is needed to ensure correct results. (Can be specific for a certain architecture, such as 32 bit ints need so many bits of floating point precision).

But then I have to question if a floating point multiply is faster than an integer divide. Generally multiply is faster than divide, but integers also tend to be faster than floating point. Of course a lot of modern machines can probably do them in about just as many clock cycles now.


At any rate it's not quite the answer I was thinking of, but the idea is fairly close. The way I know is never slower on any machine I've ever seen (although possibly not faster on some). As a bit of a hint, you don't actually need floating point to do this.  :ph34r:

Psst, computer don't really have a true "integer" data type (integers are infinite, but computer memory is finite). Rather they have equivalence classes of integers modulo some value. That is, mod 2^W, where W is the word size, such as 32 bits. Think wrap around.



I have no idea what you're doing for this second challenge, but it looks like complete nonsense to me at the moment. It sounds like you're saying -5 is 11 - 101i in base -1 + i. But isn't that kinda like saying -5 is not an integer because it has an imaginary part to it?

As for the ordered pairs, I don't think you're using them in a format that is correct for the challenge. If a number x is expressed in base b with n digits, then it can be written as a string (excuse the delimiters for clarity) <x_n-1, ..., x_2, x_1, x_0>. The value of this number is then x = x_n-1 * b^(n-1) + ... + x_2 * b^2 + x_1 * b + x_0.

Remember last post I gave the bit representations of 0, 1, -1 + i, and i, in the base -1 + i format. They are the first four 2 bit strings.

So the bit strings would be as follows:
00: 0 * (-1 + i) + 0 * (1) = 0
01: 0 * (-1 + i) + 1 * (1) = 1
10: 1 * (-1 + i) + 0 * (1) = -1 + i
11: 1 * (-1 + i) + 1 * (1) = i

Completing this table is fairly easy using the formula above. The inverse table is a little harder however.