tag:blogger.com,1999:blog-11295132.post7790745507221255597..comments2015-12-23T12:32:50.863-08:00Comments on A Neighborhood of Infinity: Optimising pointer subtraction with 2-adic integers.Dan Piponihttps://plus.google.com/107913314994758123748noreply@blogger.comBlogger24125tag:blogger.com,1999:blog-11295132.post-73912750109080891082010-05-29T00:22:51.899-07:002010-05-29T00:22:51.899-07:00Dan,
Sure for even numbers. I should have slept m...Dan,<br /><br />Sure for even numbers. I should have slept more, I did not even spot your original comment :)Cedrickhttp://www.blogger.com/profile/13226709927139593284noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-71701389818284687012010-05-28T22:41:36.480-07:002010-05-28T22:41:36.480-07:00Cedrick,
(1)
(1-x)(1+x+x^2+...+x^31)=1-x^32
If ...Cedrick,<br /><br />(1)<br /><br />(1-x)(1+x+x^2+...+x^31)=1-x^32<br /><br />If x is even x^32=0 mod 2^32, and so 1/(1-x) = 1+x+x^2+...+x^31.<br /><br />Alternatively:<br /><br />(2)<br /><br />From the 2-adic perspective, if x is even, the terms of the series are getting 'smaller' and 'smaller', so the infinite series converges. This is really just another way of saying (1), but in disguise.sigfpehttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-61718207117012601912010-05-28T19:22:52.907-07:002010-05-28T19:22:52.907-07:00tlawson this is the same method as me except that ...tlawson this is the same method as me except that I did not feel comfortable using the second = sign in 1/(1-8) = 1 + 8 + 8^2 + 8^3 + ...<br />hence my manual development.<br /><br />What makes you feel comfortable using that equality? You can justify it a posteriori but seems not obvious to me that 1/(1-x) =series(x^n) [2^32] when 1<x .<br /><br />Dan about R's method: 2^3 = 1 [7]<br />And therefore 2^3k = 1 [7] so the result appears magically by itself.Cedrickhttp://www.blogger.com/profile/13226709927139593284noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-19286925133667020842010-05-28T18:58:19.811-07:002010-05-28T18:58:19.811-07:00tlawson,
Nice one! BTW It works for any odd integ...tlawson,<br /><br />Nice one! BTW It works for any odd integer, but it goes faster for one less than a power of two. I should have picked a harder example than 7 :-)sigfpehttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-90193028387243684002010-05-28T18:20:07.219-07:002010-05-28T18:20:07.219-07:00Quick comment: In this case, you can invert -7 pre...Quick comment: In this case, you can invert -7 pretty easily using the geometric series.<br /><br />-1/7 = 1/(1-8) = 1 + 8 + 8^2 + 8^3 + ...<br /><br />which converges 2-adically ....1001001001001001. Then get 1/7 by taking the "2's complement" negative.tlawsonhttp://www.blogger.com/profile/13979554472460966899noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-36788582859112548052010-05-26T13:08:27.404-07:002010-05-26T13:08:27.404-07:00You are correct, of course, I now realize that wha...You are correct, of course, I now realize that what I wrote is trivial. I used trial and error, which didn't take too long, obviously - 2^33-1 is the second choice, right after 2^32-1 which didn't work. Note that I'm trying to describe how a human being might reach this particular number, not how a computer could solve the general case.<br /><br />This did get me thinking, however, about long division: Divide 11111... by b in binary (in this case, b=7) and stop where the remainder is zero (after at least 32 bits). I don't know if this will always work when b is odd (it will never work when b is even, of course).<br /><br />Apologies if I'm being trivial again, or just plain wrong.Rhttp://www.blogger.com/profile/05404933714236342658noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-91409840868318929302010-05-26T12:49:23.922-07:002010-05-26T12:49:23.922-07:00@R,
This
"a+1=0 [mod 2^32], and (2) a is di...@R,<br /><br />This<br /><br />"a+1=0 [mod 2^32], and (2) a is divisible by 7"<br /><br />is essentially a restatement of the original problem: we're trying to find a such that 7a=1 mod 2^32. 2^33-1 is a solution, so that explains why gcc chose the constant for this particular example. But what method are you proposing to find this solution?sigfpehttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-45495960245856516592010-05-26T12:36:29.220-07:002010-05-26T12:36:29.220-07:00A simpler way to find the number, based on Cedrick...A simpler way to find the number, based on Cedrick's method, is as follows:<br /><br />x = 7y<br />y = (a+1)y - ay = (a+1)y - (a/7)x<br /><br />We want to choose a such that (1) a+1=0 [mod 2^32], and (2) a is divisible by 7. It turns out that a=2^33-1 is such a number, and a/7=1227133513. This means that mod 2^32,<br /><br />y = -(a/7)x = -1227133513xRhttp://www.blogger.com/profile/05404933714236342658noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-65580345240570322122010-05-25T22:09:47.207-07:002010-05-25T22:09:47.207-07:00@BlackMeph Yes, well spotted. Substitute 'no&#...@BlackMeph Yes, well spotted. Substitute 'no' for 'a'.sigfpehttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-36552491649697354772010-05-25T21:48:58.042-07:002010-05-25T21:48:58.042-07:00@sigfpe, in your reply to Cedrick, dated 17 May 20...@sigfpe, in your reply to Cedrick, dated 17 May 2010, where you said, "Some of the real numbers have a square root, some have two, and zero has just one." should the "a" above be a "no", perhaps?BlackMephhttp://www.blogger.com/profile/02745499320156194052noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-49638344373108281532010-05-23T14:15:41.675-07:002010-05-23T14:15:41.675-07:00Cory,
Which exact sentence do you think I wrote i...Cory,<br /><br />Which exact sentence do you think I wrote incorrectly? I'm a bit blind when it comes to spotting my own typos.sigfpehttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-64985360232028317072010-05-21T17:38:39.414-07:002010-05-21T17:38:39.414-07:00I'll repeat the "Great post, Dan" co...I'll repeat the "Great post, Dan" comment. You continue to amaze me with the examples and situations you use to motivate abstract concepts.<br /><br />One problem, though: you say the rationals are constructed using Cauchy sequences. Do you, perhaps, mean the reals?Coryhttp://www.blogger.com/profile/00719239141281769751noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-12401583898566411332010-05-20T11:55:39.295-07:002010-05-20T11:55:39.295-07:00@ardencaple You can see the Newton method if you v...@ardencaple You can see the Newton method if you view the source to <a href="http://www.hackersdelight.org/magic.htm" rel="nofollow">this</a> page.sigfpehttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-51152333409624160732010-05-20T11:31:39.730-07:002010-05-20T11:31:39.730-07:00There is also a rather more 'hacky' introd...There is also a rather more 'hacky' introduction to this in the book and site<br />'Hacker's Delight'<br /><br />http://www.hackersdelight.org/<br /><br />See the section on 'Magic Numbers'ardencaplehttp://www.blogger.com/profile/13736065720146542604noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-79512439437189182522010-05-20T06:42:17.451-07:002010-05-20T06:42:17.451-07:00@Gery I'll fix that. When first I learnt about...@Gery I'll fix that. When first I learnt about p-adics I was using direct/inverse limit language but these days I use limit/colimit language. It drives me crazy that *co*limit corresponds to *inverse* limit.sigfpehttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-47667577102003659702010-05-20T06:41:10.907-07:002010-05-20T06:41:10.907-07:00I received a post from a user called Gery but it w...I received a post from a user called Gery but it was attached to the wrong blog post so I'm posting it here:<br /><br />The colimit of your diagram is simply the Intel 4004 while the limit of the same diagram is an hypothetical infinite machine which projects onto every finite machines.<br /><br />So, I guess you meant to talk about limits, instead of colimits.sigfpehttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-26635682517536560372010-05-18T12:28:18.616-07:002010-05-18T12:28:18.616-07:00Great post, thank you. I had never studied p-adic ...Great post, thank you. I had never studied p-adic numbers and had only encountered them a few times; I thought they were just a curiosity and didn't realise they had applications. Hensel's lemma is really cool.<br /><br />[BTW, I'm not a lawyer, but as I understand it, in general, the only requirements of images under free licenses (like most images on Wikipedia, except a few that are used as "fair use") are that<br /><br />1. You credit the author. GFDL or Creative Commons aren't very clear on how to do this, but Wikipedia simply arranges so that clicking on the image will take you to a page that has author information, and if you link to the same page, it should be ok. (Or better, also add a line under the image crediting the author credited on Wikipedia.)<br /><br />2. Copyleft. "If you alter, transform, or build upon this work, you may distribute the resulting work only under the same or similar license to this one." (The strictest and possibly incorrect interpretation would be that including the image makes your blog post freely licensed as well, but I don't think so.)]displaynamehttp://www.blogger.com/profile/09068351772472305473noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-25933845976881080102010-05-17T11:19:06.933-07:002010-05-17T11:19:06.933-07:00jisakujien
> Is it really that hard to have a ...jisakujien<br /><br />> Is it really that hard to have a link to the original image pages with their licensing info?<br /><br />Yes it is. Not because linking is hard, but because I don't have a lawyer to tell me whether that is an acceptable solution either. I'll replace these images with public domain images within 12 hours and I appreciate that with your prompting I will then be 100% legal. Thanks for setting me straight.sigfpehttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-49408287903542859122010-05-17T10:52:13.869-07:002010-05-17T10:52:13.869-07:00Just linking to a page about the GFDL (which isn&#...Just linking to a page about the GFDL (which isn't even the text of the GFDL--not that that would be sufficient either) is not enough. There are quite a lot of hoops that you have to jump through that not even Wikipedia itself gets right.<br /><br />You also have the problem that the images used in Wikipedia are not necessarily available under the GFDL in the first place.<br /><br />Thankfully, Wikipedia has <a href="http://meta.wikimedia.org/wiki/Licensing_update" rel="nofollow">transitioned</a> to also using <a href="http://creativecommons.org/licenses/by-sa/3.0/" rel="nofollow">CC-BY-SA-3.0</a> which is much simpler to understand and meet the requirements of (with the caveat that the transition itself complicates things to some extent). Because of this, you really should take the small amount of effort to at least read the non-legal text of the license and attempt to follow it. <br /><br />Just saying 'oh, it is too hard and confusing' while making no real effort is quite dishonest. Saying that you took various images from Wikipedia and they might be available under some license isn't even a nominal attempt. Is it really that hard to have a link to the <a href="http://en.wikipedia.org/wiki/File:MOS_6502AD_4585_top.jpg" rel="nofollow">original image pages with their licensing info</a>? That would at least be a good faith effort.jisakujienhttp://www.blogger.com/profile/16512853074147028868noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-30498847703320879692010-05-17T07:24:26.729-07:002010-05-17T07:24:26.729-07:00Cedrick,
I did drop a big hint when I said "...Cedrick,<br /><br />I did drop a big hint when I said "any problems?" :-) The situation roughly mimics the situation with the real numbers. Some of the real numbers have a square root, some have two, and zero has just one.<br /><br />Anyway, I like your method as it's very easy to understand. But the Newton method here is very easy to code up (one short line of code), and runs fast.sigfpehttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-15898225879725288322010-05-16T22:42:56.340-07:002010-05-16T22:42:56.340-07:00This comment has been removed by a blog administrator.Cedrickhttp://www.blogger.com/profile/13226709927139593284noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-79609983164566332762010-05-16T22:42:56.338-07:002010-05-16T22:42:56.338-07:00Andrej, yes you could use Euclid algorithm but I t...Andrej, yes you could use Euclid algorithm but I think my calculation is easier and less error prone.<br /><br />Since Dan mentioned first principles, it led me to try to find the simplest and easiest method to find the positive number n so that n * 7 = 1 [2^32] and I found that the easiest way could be done by kids in 4th or 5th grade without knowledge of Euclid or Bezout.<br /><br />Looking for the number in hexadecimal is the easiest way due to the modulo. Write the products of 1 to F with 7 you get 7, e, 15, 1c, 23, 2a, 31, 38, 3f, 46, 4d, 54, 5b, 62 and 69.<br /><br />Since the last digit of the product number with 7 is 1 only 7 works, so you have the last digit.<br />Now ?7 x 7 = 01, given that 7x7 was 31, you need the last digit of the multiplication of ? and 7 to be 10 - 3 = D which comes from Bx7.<br />You repeat the same procedure with ?B7 x 7 = 001, and you finally reach B6DB6DB7.<br /><br />I am interested by any simpler method.<br /><br />Dan, not sure if I understood the challenge about the square root since with the method above I can prove that there is no square root for 7.Cedrickhttp://www.blogger.com/profile/13226709927139593284noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-23769261025635312462010-05-15T23:06:10.325-07:002010-05-15T23:06:10.325-07:00I thought you were going to say that -1227133513 i...I thought you were going to say that -1227133513 is the inverse of 7 in the ring Z/(2^32 Z) of integers modulo 2^32, i.e., since -1227133513 * 7 == 1 mod 2^32 dividing by 7 is the same as multiplying by -1227133513. The number -1227133513 may be computed with Euclid's algorithm.<br /><br />P.S. I think that - in the source code should be /.Andrej Bauerhttp://www.blogger.com/profile/17920316604280193336noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-19200019294183337202010-05-15T22:58:57.045-07:002010-05-15T22:58:57.045-07:00Great post Dan, and very interesting.
First of al...Great post Dan, and very interesting.<br /><br />First of all, it is important to note that the GCC code is not a general answer to the division by 7, the formula only works for numbers exactly divisible by 7.<br /><br />You can find this without the need of Newton. I actually was asked that question in my first interview in the U.S. and below is how I quickly derived it during the interview. Funnily enough, the interviewers did not expect that such a solution could exist :)<br /><br />x = 7y<br />x = 8y - y<br /><br />y = 8y - x = 2^3*y - x (1)<br /><br />Multiplying (1) by 2^3 gives<br /><br />2^3*y = 2^6*y - 2^3*x (2)<br /><br />Using (2) in (1) gives<br /><br />y = 2^6*y - x - 2^3*x<br /><br />Repeating the same procedure 10 times gives<br /><br />y = 2^33*y - x - 2^3*x - 2^6*x - 2^9*x - 2^12*x - 2^15*x - 2^18*x - 2^21*x - 2^24*x - 2^27*x - 2^30*x<br /><br />Since we are working with 32 bits numbers we are working modulo 2^32 and therefore 2^33*y = 0 [2^32]<br /><br />Therefore y = - x - 2^3*x - 2^6*x - 2^9*x - 2^12*x - 2^15*x - 2^18*x - 2^21*x - 2^24*x - 2^27*x - 2^30*x<br /><br />And then y = x * -( 1 + 2^3 + 2^6 + 2^9 + 2^12 + 2^15 + 2^18 + 2^21 + 2^24 + 2^27 + 2^30 )<br /><br />y = x * -1227133513<br /><br />You can use the same method to derive a method that works for all integers. And I leave the challenge to the readers that works for all integers without the use of the multiplication :)<br /><br />CedrickCedrickhttp://www.blogger.com/profile/13226709927139593284noreply@blogger.com