flat assembler
Message board for the users of flat assembler.

Index > Heap > Nearly All Binary Searches Searches and Mergesorts are Broke

Author
Thread Post new topic Reply to topic
LocoDelAssembly
Your code has a bug


Joined: 06 May 2005
Posts: 4633
Location: Argentina
LocoDelAssembly
Post 16 Jun 2006, 00:54
View user's profile Send private message Reply with quote
Madis731



Joined: 25 Sep 2003
Posts: 2140
Location: Estonia
Madis731
The only problem is that I rarely use signed integers in assembly coding and these bugs never happen. You would argue, of course, that its only trying to hide the bug and you are correct: I can only manage to push 2^31-1 limit to 2^32-1 but there have been algorithms to find average FOR AGES. You can find them in any programming gems.

I think it should be forbidden to use the AVG(A,B)=(A+B)/2 approach. The first thing you can do is A/2+B/2, but there are even simpler solutions. You can take into account the carry and when you do:
Code:
mov  eax,0FEDCBA98h ;Init
mov  ebx,076543210h

add  eax,ebx
rcr  eax,1
    

...there you have it! AND you even have the carry to flag you that the average was not an integer Wink
Post 16 Jun 2006, 11:18
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
Tomasz Grysztar



Joined: 16 Jun 2003
Posts: 7740
Location: Kraków, Poland
Tomasz Grysztar
Madis731: It's a brilliant demonstration of assembly advantages. Wink
Post 16 Jun 2006, 12:53
View user's profile Send private message Visit poster's website Reply with quote
tom tobias



Joined: 09 Sep 2003
Posts: 1320
Location: usa
tom tobias
Donald Knuth: Art of Computer Programming, Volume 3: Sorting and Searching (2nd Edition) Addison Wesley 1998
http://www.amazon.com/gp/product/0201896850/102-5961767-1807363?v=glance&n=283155
Smile
Post 16 Jun 2006, 13:08
View user's profile Send private message Reply with quote
vid
Verbosity in development


Joined: 05 Sep 2003
Posts: 7105
Location: Slovakia
vid
yes, it's probable best argument for asm vs. C. In C you can't do overflow handling, which can result in some unavoidable error (when you can't predict what operations will you do with numbers, and thus what range of numbers allowed not to overflow).

friend of mine, C-ist, said it's because some processors don't support overflow checking.


Last edited by vid on 05 Feb 2007, 17:20; edited 1 time in total
Post 16 Jun 2006, 14:23
View user's profile Send private message Visit poster's website AIM Address MSN Messenger ICQ Number Reply with quote
LocoDelAssembly
Your code has a bug


Joined: 06 May 2005
Posts: 4633
Location: Argentina
LocoDelAssembly
In case of using integers http://www.pagetable.com/?p=20
Post 05 Feb 2007, 15:47
View user's profile Send private message Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  


< Last Thread | Next Thread >
Forum Rules:
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 vote in polls in this forum
You can attach files in this forum
You can download files in this forum


Copyright © 1999-2020, Tomasz Grysztar. Also on YouTube, Twitter.

Website powered by rwasa.