{"id":62,"date":"2008-04-25T11:15:10","date_gmt":"2008-04-25T13:15:10","guid":{"rendered":"http:\/\/www.ragestorm.net\/blogs\/?p=62"},"modified":"2008-04-25T11:16:12","modified_gmt":"2008-04-25T13:16:12","slug":"signed-division-in-python-and-vial","status":"publish","type":"post","link":"https:\/\/www.ragestorm.net\/blogs\/?p=62","title":{"rendered":"Signed Division In Python (and Vial)"},"content":{"rendered":"

My stupid hosting company decided to\u00a0move the site to a different server blah blah, the point\u00a0is that I lost some of the recent DB changes and my email hasn’t been working for a week now :(<\/font><\/small><\/h3>\n

Anyways I repost it. The sad truth was that I had to find the post in Google’s cache in order to restore it, way to go.<\/font><\/small><\/h3>\n

<\/small>Friday, April 18th, 2008:<\/font><\/small><\/h3>\n

As I was working on Vial to implement the IDIV instruction, I needed to have a signed division operator in Python. And since the x86 is a 2\u2019s complement based, I first have to convert the number into Python\u2019s negative (from unsigned) and only then make the operation, in my case a simple division. It was supposed to be a matter of a few minutes to code this function which gets the two operands of IDIV and return the result, but in practice it took a few bad hours.<\/p>\n

The conversion is really easy, say we mess with 8 bits integers, then 0xff is -1, and 0\u00d780 is -128 etc. The equation to convert it to a Python\u2019s negative is: val – (1 << sizeof(val)*8). Of course, you do that only if the most significant bit, sign bit, is set. Eventually you return the result of val1 \/ val2. So far so good, but no, as I was trying to feed my IDIV with random input numbers, I saw that the result my Python\u2019s code returns is not the same as the processor\u2019s. This was when I started to freak out. Trying to figure out what\u2019s the problem with my very simple snippet of code. And alas, later on I realized nothing was wrong with my code, it\u2019s all Python\u2019s fault.<\/p>\n

What\u2019s wrong with Python\u2019s divide operator? Well, to be strict, it does not round the negative result toward 0, but towards negative infinity. Now, to be honest, I\u2019m not really into math stuff, but all x86 processors rounds negative numbers (and positive also to be accurate) toward 0. So one would really assume Python does the same, as would C, for instance. The simple case to show what I mean is: 5\/-3, in Python results in -2. Rather than -1, as the x86 IDIV instruction is expected and should return. And besides -(5\/3) is not 5\/-3 in Python, now it\u2019s the time you say WTF. Which is another annoying point. But again, as I\u2019m not a math guy, though I was speaking with many friends about this behavior, that equality (or to be accurate, inequality) is ok in real world. Seriously, what we, coders, care about real world math now? I just want to simulate a simple instruction. I really wanted to go and shout \u201chey there\u2019s a bug in Python divide operator\u201d and how come nobody saw it before? But after some digging, this behavior is really documented in Python. As much as I would hate it and many other people I know, that\u2019s that. I even took a look at the source code of the integer division algorithm, and saw a \u2018patch\u2019 to fix the numbers to be floored if the result is negative because of C89 doesn\u2019t define the rounding well enough.<\/p>\n

While you\u2019re coding something and you have a bug, you usually just start debugging your code and track it down and then fix it easily while keeping on working on the code. Because you\u2019re in the middle of the coding phase. There are those rare times that you really get crazy when you\u2019re absolutely sure your code is supposed to work (which it does not) and then you realize that the layer you should trust is broken (in a way). Really you want kill someone\u00a0 \u2026 being a good guy I won\u2019t do that.<\/p>\n

Did I hear anyone say modulo?? Oh don\u2019t even bother, but this time I think that Python returns the (math) expected result rather than the CPU. But what does it matter now? I really want only to imitate the processor\u2019s behavior. So I had to hack that one too.<\/p>\n

The solution after all, was to make the Python\u2019s negative number to be absolute and remember its original sign, that we do for both operands. And then we make an unsigned division and if the signs of the input are not the same we change the sign of the result. This is because we know that the unsigned division works as the processor does and we can then use it safely.<\/p>\n

res = x\/y; if (sign_of_x != sign_of_y) res = -res;<\/p>\n

The bottom line is that I really hate this behavior in Python and it\u2019s not a bug, after all. I\u2019m not sure how many people like me encountered this issue. But it\u2019s really annoying. I don\u2019t believe they are going to fix it in Python 3, never know though.<\/p>\n

Anyway, I got my IDIV working now, and that was the last instruction I had to cover in my unit tests. Now It\u2019s analysis time :)<\/p>\n","protected":false},"excerpt":{"rendered":"

My stupid hosting company decided to\u00a0move the site to a different server blah blah, the point\u00a0is that I lost some of the recent DB changes and my email hasn’t been working for a week now :( Anyways I repost it. The sad truth was that I had to find the post in Google’s cache in […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"spay_email":"","jetpack_publicize_message":""},"categories":[21,5,19,9],"tags":[],"jetpack_featured_media_url":"","jetpack_publicize_connections":[],"jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/pbWKd-10","_links":{"self":[{"href":"https:\/\/www.ragestorm.net\/blogs\/index.php?rest_route=\/wp\/v2\/posts\/62"}],"collection":[{"href":"https:\/\/www.ragestorm.net\/blogs\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.ragestorm.net\/blogs\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.ragestorm.net\/blogs\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.ragestorm.net\/blogs\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=62"}],"version-history":[{"count":0,"href":"https:\/\/www.ragestorm.net\/blogs\/index.php?rest_route=\/wp\/v2\/posts\/62\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.ragestorm.net\/blogs\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=62"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.ragestorm.net\/blogs\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=62"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.ragestorm.net\/blogs\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=62"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}