Online since 2002. Over 3300 puzzles, 2600 worldwide members, and 270,000 messages.

TwistyPuzzles.com Forum

It is currently Sat Apr 19, 2014 12:29 pm

All times are UTC - 5 hours



Post new topic Reply to topic  [ 8 posts ] 
Author Message
 Post subject: I discovered a new type of puzzle, you should try it
PostPosted: Tue Sep 27, 2011 4:56 am 
Offline
User avatar

Joined: Tue Jan 06, 2009 7:23 pm
x86 assembly. Its like a giant 15 puzzle, but with 8 slots instead of 15 and all sorts of tricks and rules you can use to change the board. You should try it some time :lol:

my assignment: take this c++ loop for calculating the Mandelbrot set and optomize it using assembly

COLORREF render_point(double x, double y, int N)
{
double a = 0.0, b = 0.0, norm2 = 0.0;
int n;
for (n = 0; norm2 < 4.0 && n < N; ++n)
{
//you only need to convert this inside loop, but you can do the whole thing
double c = a*a - b*b + x;
b = 2.0*a*b + y;
a = c;
norm2 = a*a + b*b;
}
//remember to clear your registers
int value = int(255*(1 - double(n)/N));
return RGB(value,value,value);
}
i was able to do it in 31 assembly lines (more like 60, i had to restart once) and it was so much fun
i cant give out full implementation, my school makes us copyright and hold on to all of our code, but i was able to make my program a few seconds faster with it, and it felt like i was playing a game of rush hour mixed with a 15 puzzle. You coders should give a try, just for fun, assembly is way more fun than i thought :wink:

-Nick

_________________
Image


Top
 Profile  
 
 Post subject: Re: I discovered a new type of puzzle, you should try it
PostPosted: Tue Sep 27, 2011 10:49 pm 
Offline
User avatar

Joined: Thu Dec 21, 2006 5:32 pm
Location: Bay Area, CA
x86 meaning 8086 (16 bit, ax, bx etc.) or 386+ which allows 32 bit registers (eax, ebx, etc.)? Would an x87 co-processor be available?

Doing this in true 8086 without the co-processor would be a bit complicated because the numbers are doubles (and not in 31 instructions, I would guess!).

Many years back I wrote an x86 16 bit register based IEEE754 compliant 32 bit floating point library (args passed in ax:bx, cx:dx). It was really fast because it didn't use any stack variables (remember kids: In assembly memory is the slow stuff), but certainly involved a lot of careful register swapping...

Dave

_________________
Image
LitwinPuzzles.com has info on my puzzles.


Top
 Profile  
 
 Post subject: Re: I discovered a new type of puzzle, you should try it
PostPosted: Wed Sep 28, 2011 4:08 am 
Offline
User avatar

Joined: Thu Sep 17, 2009 6:07 am
Location: Germany, Bavaria
DLitwin wrote:
...Many years back I wrote an x86 16 bit register based IEEE754 compliant 32 bit floating point library....Dave
Many years back, I have ported UNIX (ok XENIX from Microsoft) to a 8086 system and later to a 80186 system. Quite an adventure! Memory 256 KB - 1024 MB. 10 MB hard disk.
Can you even imagine this, kids? :lol:
Now, that had been "real programming".

_________________
My collection at: http://sites.google.com/site/twistykon/home


Top
 Profile  
 
 Post subject: Re: I discovered a new type of puzzle, you should try it
PostPosted: Wed Sep 28, 2011 10:05 am 
Offline
User avatar

Joined: Tue Jan 06, 2009 7:23 pm
DLitwin wrote:
x86 meaning 8086 (16 bit, ax, bx etc.) or 386+ which allows 32 bit registers (eax, ebx, etc.)? Would an x87 co-processor be available?

Doing this in true 8086 without the co-processor would be a bit complicated because the numbers are doubles (and not in 31 instructions, I would guess!).

Many years back I wrote an x86 16 bit register based IEEE754 compliant 32 bit floating point library (args passed in ax:bx, cx:dx). It was really fast because it didn't use any stack variables (remember kids: In assembly memory is the slow stuff), but certainly involved a lot of careful register swapping...

Dave


Indeed i did forget to mention a few details. The assignment was to be done entirely on the fpu (unless you wanted to write the loop in assembly as well) . And you werent supposed to write any of the variables back except norm2 at the end of each loop, all the other calculated variables needed to stay in the registers and be updated and popped so that when the loop continued the variables were in the same location as where they began. And im still new to assembly so, i didnt understand everything you were saying :wink:

_________________
Image


Top
 Profile  
 
 Post subject: Re: I discovered a new type of puzzle, you should try it
PostPosted: Wed Sep 28, 2011 5:39 pm 
Offline

Joined: Sun Nov 23, 2008 2:18 am
I took a semester of x86 assembly back in Spring 2007, but I would have to do some serious refreshing to do anything useful.

_________________
Just so you know, I am blind.

I pledge allegiance to the whole of humanity, and to the world in which we live: one people under the heavens, indivisible, with Liberty and Equality for all.

My Shapeways Shop


Top
 Profile  
 
 Post subject: Re: I discovered a new type of puzzle, you should try it
PostPosted: Wed Sep 28, 2011 7:37 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
It's good to know there are other geeks here that like to get their hands dirty.

I have spent far more time reverse engineering compiled code than I have writing x86. Compilers often generate the worst most offensive x86 you could imagine.

My California license plate is "PUSH ECX" :)

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: I discovered a new type of puzzle, you should try it
PostPosted: Fri Sep 30, 2011 11:25 pm 
Offline
User avatar

Joined: Thu Dec 21, 2006 5:32 pm
Location: Bay Area, CA
bmenrigh wrote:
Compilers often generate the worst most offensive x86 you could imagine.
One of the points made early in Michael Abrash's Zen of Assembly Language is that the architecture of the x86 has complicated tradeoffs which makes it hard for a compiler to do a good job. This, then, means you have much more room to improve your code by hand written assembly than on other architectures.

Over time this has diminished as the architecture has changed, but for the early 8086 it most definitely held true.

That was a phenomenal book that I read cover to cover as a new employee at my first career job. It is a bit dated and of course very architecture specific, but if you wish to pursue the topic of this thread ("new type of puzzle" i.e. assembly) I can think of few better books that delve deep into the process of optimizing: Gaining a deep understanding of the tools you have (i.e. instruction set), optimizing to do less work (not more work faster), and how real timing of running code always beats out abstract cycle counting or theoretical gains.

Dave

_________________
Image
LitwinPuzzles.com has info on my puzzles.


Top
 Profile  
 
 Post subject: Re: I discovered a new type of puzzle, you should try it
PostPosted: Sun Oct 02, 2011 11:45 pm 
Offline
User avatar

Joined: Sun Mar 11, 2007 3:11 am
Location: Oregon, USA
Here's a semi-historical puzzle about the x86 series: why does the opcode map have an unexplained gap at byte D6?

This empty gap at D6 first appeared in the manuals for the 8086/88 over thirty years ago, and it's been left empty in every subsequent generation until the entire map was redefined for the 64-bit operation. And this, despite continual pressure to free up first-bytes for use as new instructions, multi-byte escapes, prefixes, optimization hints, etc.

Why weren't there any instructions or prefixes staring with D6 for over three decades?

(Note: it was inadvertently documented in Intel's first P6 architecture manual, but dropped from subsequent editions)

_________________
See my blog about 3D printing puzzles at MySD300


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 8 posts ] 

All times are UTC - 5 hours


Who is online

Users browsing this forum: No registered users and 2 guests


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:  

Forum powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group