tag:blogger.com,1999:blog-835341608950140555.comments2013-08-13T14:52:46.290+02:00Numerical RecipesJaimehttp://www.blogger.com/profile/02831887559711602902noreply@blogger.comBlogger26125tag:blogger.com,1999:blog-835341608950140555.post-49757010722290407152013-08-13T14:12:00.427+02:002013-08-13T14:12:00.427+02:00This comment has been removed by the author.3 Wheelshttp://www.blogger.com/profile/01987266225086034095noreply@blogger.comtag:blogger.com,1999:blog-835341608950140555.post-2346542108307960792012-04-30T05:21:03.179+02:002012-04-30T05:21:03.179+02:00can you give me the output of your calls to testMo...can you give me the output of your calls to testModInv?Dannohttp://www.blogger.com/profile/07370205056721374906noreply@blogger.comtag:blogger.com,1999:blog-835341608950140555.post-14543868131958851042011-04-17T00:37:46.440+02:002011-04-17T00:37:46.440+02:00Couple years late but this page has been great hel...Couple years late but this page has been great help for a university project!<br /><br />This is my implementation of your functions, I find it runs around 25% faster simply by referencing methods outside of loops:<br /><br />http://pastebin.com/BmHuMwEq<br /><br />I'm still trying to figure out a way of using reduce/list-comprehension to get rid of as much of the loop overhead as possible.<br /><br />Oh, and finally, dft(x) is kinda a moot point, as I'm padding everything I feed to fft_CT(x) with 0s to make the list length a power of 2.Vesuvianhttp://www.blogger.com/profile/05706498021508071759noreply@blogger.comtag:blogger.com,1999:blog-835341608950140555.post-68440643868564434192009-11-04T15:41:49.963+01:002009-11-04T15:41:49.963+01:00hi!
i need to calculate a fft of a matrix. actuall...hi!<br />i need to calculate a fft of a matrix. actually i need it as a part of my program.<br /><br />i read really a lot of different books and inernet pages on the subject of fft, but i still don't know how to use it.<br />i understand why you split the dft, and all related to that, but when it comes to the exact calculations... i just don't know what to do with it.<br /><br />could you help me please? <br />this is my email:<br /><br />kviki_kiki@yahoo.com<br /><br />thanksKikahttp://www.blogger.com/profile/17516856671638207929noreply@blogger.comtag:blogger.com,1999:blog-835341608950140555.post-47982670349963103422009-05-01T21:34:00.000+02:002009-05-01T21:34:00.000+02:00I was using Aex Gorbatchev's Syntax Highlighter. G...I was using <A HREF="http://alexgorbatchev.com/wiki/SyntaxHighlighter" REL="nofollow">Aex Gorbatchev's Syntax Highlighter</A>. Great looking, easy to setup, and there's even a public server if you don't have a place to host the files.<br /><br />It comes as standard in Wordpress...numericalrecipeshttp://numericalrecipes.wordpress.com/noreply@blogger.comtag:blogger.com,1999:blog-835341608950140555.post-20383598711968306862009-05-01T20:12:00.000+02:002009-05-01T20:12:00.000+02:00On a related topic, what were you using to format ...On a related topic, what were you using to format your code? Nothing I've tried has looked as nice as the examples you've posted.Bill the Lizardhttp://www.blogger.com/profile/09810099093752485841noreply@blogger.comtag:blogger.com,1999:blog-835341608950140555.post-68300105165241929002009-04-30T18:33:00.000+02:002009-04-30T18:33:00.000+02:00You can use Google Analytics with self-hosted Word...You can use Google Analytics with self-hosted WordPress. I don't know about blogs hosted by WordPress.com.Johnhttp://www.blogger.com/profile/07480208135315956118noreply@blogger.comtag:blogger.com,1999:blog-835341608950140555.post-52286007619274769112009-04-18T08:08:00.000+02:002009-04-18T08:08:00.000+02:00I find your explanation a little confusing. At fi...I find your explanation a little confusing. At first it isn't clear why splitting the DFT sum into two pieces saves us any work... eventually you mention the "detail" that the periodicity of the transform means we only have to calculate the two sums for k up to M-1 rather than N-1. But it is precisely this fact which cuts the work in half.<br /><br />Also I'm pretty sure in the first code listing, lines 13 and 14 should be indented one level deeper. That way all elements of X get divided (for the inverse transform) instead of just the final one!Greg Ballhttp://www.blogger.com/profile/06661985258561000968noreply@blogger.comtag:blogger.com,1999:blog-835341608950140555.post-55840607196824802852009-04-17T02:17:00.000+02:002009-04-17T02:17:00.000+02:00Just to point out a typo: it's "Tukey" not "Turkey...Just to point out a typo: it's "Tukey" not "Turkey". The co-inventor of the FFT was called John Tukey:<br /><br />http://en.wikipedia.org/wiki/John_Tukeystochastixhttp://stochastix.wordpress.com/noreply@blogger.comtag:blogger.com,1999:blog-835341608950140555.post-31497563541934748342009-04-17T01:52:00.000+02:002009-04-17T01:52:00.000+02:00I'm afraid I hit the "publish" button a little too...I'm afraid I hit the "publish" button a little too fast, and you saw a big work-in-progress mess...<br /><br />I have started using MathTran (http://www.mathtran.org) to display TeX on the blog, since plain text wasn't an alternative for FFTs. It does have the reader problem, similar to what goes on with the syntax highlighter, which only works in the blog, not in the reader.<br /><br />I'm not too happy with this solution as it is, so I may go back to generating image files for the formulas off-line and uploading them (the ones you saw nicely on your reader), although it turns producing a math intensive post into a nightmare, specially if you have, as I do, a tendency to spot mistakes very late...Jaimehttp://www.blogger.com/profile/02831887559711602902noreply@blogger.comtag:blogger.com,1999:blog-835341608950140555.post-52628312037715391942009-04-16T22:58:00.000+02:002009-04-16T22:58:00.000+02:00Jaime,
Your first equation shows up in Google Re...Jaime, <br /><br />Your first equation shows up in Google Reader as "tex: X_k \pi" but the other four equations show up as nice graphics. The first equation looks fine when I go directly to your web site, just not in my reader. Is something different about your first TeX expression?Johnhttp://www.blogger.com/profile/07480208135315956118noreply@blogger.comtag:blogger.com,1999:blog-835341608950140555.post-45405552547096730012009-03-29T08:34:00.000+02:002009-03-29T08:34:00.000+02:00Another way to boost performance using Python 2.6 ...Another way to boost performance using Python 2.6 and higher is to use the new bytearray data type.<BR/>Simply change<BR/> sieve = [True for j in xrange(maxI+1)]<BR/>to<BR/> sieve = bytearray([1 for j in xrange(maxI+1)])<BR/>For me it reduced CPU time by 9% and maximum memory use by 28%.bwwsNfoNlfTu8_kcwzbIoZ7TzCm0Ku7.https://me.yahoo.com/a/bwwsNfoNlfTu8_kcwzbIoZ7TzCm0Ku7.#e2bb4noreply@blogger.comtag:blogger.com,1999:blog-835341608950140555.post-55668738778581213612009-03-26T03:28:00.000+01:002009-03-26T03:28:00.000+01:00Another way to reduce memory use is to use the sta...Another way to reduce memory use is to use the standard Python array module instead of a list of booleans for the sieve.<BR/><BR/># 8-bit unsigned int<BR/>sieve = array.array('B', [1] * (maxI+1))<BR/>array0 = array.array('B', [0])<BR/>...<BR/> sieve[k] = array0<BR/><BR/>It reduces memory use by about a third (but runs slightly slower). I think the Python list data type has been optimised for speed, and the array data type (which is a useful alternative to the list, but only in specific situations) has been a bit neglected and is not optimised.<BR/><BR/>But if you are thinking of using the array module to reduce memory, then probably a better alternative is to use the third party numpy module/package - it makes the array module obsolete. Its a shame numpy is not a standard part of Python.bwwsNfoNlfTu8_kcwzbIoZ7TzCm0Ku7.https://me.yahoo.com/a/bwwsNfoNlfTu8_kcwzbIoZ7TzCm0Ku7.#e2bb4noreply@blogger.comtag:blogger.com,1999:blog-835341608950140555.post-31842974530915599722009-03-25T17:58:00.000+01:002009-03-25T17:58:00.000+01:00The xrange thing is deliberate: for some odd reaso...The xrange thing is deliberate: for some odd reason python uses less memory with the list comprehension style. I've just tried it once more, and I get a MemoryError with [True]*10**8, but not, the way I've coded it.<BR/><BR/>You are right about the sqrt thing. Worse than that, I had read, and have just verified, that the built-in exponentiation function is actually 3x faster! Not that it really affects this function, as we are doing it just once, but is definitely good practice to drop sqrt altogether...<BR/><BR/>The speed gains are probably from the slice notation, or so I read somewhere. I find it more confusing, though, but doubling the speed is probably worth the confusion.<BR/><BR/>As for the tags, I don't have a clue, as what works in the blog entries (pre, or code tags) is rejected by the comment editor...Jaimehttp://www.blogger.com/profile/02831887559711602902noreply@blogger.comtag:blogger.com,1999:blog-835341608950140555.post-21670225872943949012009-03-25T16:47:00.000+01:002009-03-25T16:47:00.000+01:00I took the last function primeListSofE and experim...I took the last function primeListSofE and experimented making some changes to it.<BR/><BR/>You don't need to import math just for sqrt since you can use 'int(n**.5)'.<BR/><BR/>You can create the sieve with<BR/>sieve = [True] * (maxI+1)<BR/>avoiding the need to iterate through xrange.<BR/><BR/>The 'p' loop can be translated into an 'i' loop; and the 'k' loop can be replaced by extended slice notation.<BR/><BR/>I ended up with:<BR/><BR/>def primeListSofE(n, verbose = False):<BR/> maxI = (n-3)//2<BR/> maxP = int(n**.5)<BR/> sieve = [True] * (maxI+1)<BR/> for i in xrange(0, (maxP-3)//2+1):<BR/> if sieve[i]:<BR/> p = 2*i+3<BR/> sieve[(p*p-3)//2::p] = [False] * ((n//p-p)//2+1)<BR/> return [2]+[2*j+3 for j in xrange(len(sieve)) if sieve[j]]<BR/><BR/>On my PC it runs about 100% faster than the original, but uses about 10% more memory.<BR/><BR/>PS. Is there some tag needed so that code examples are formatted properly?bwwsNfoNlfTu8_kcwzbIoZ7TzCm0Ku7.https://me.yahoo.com/a/bwwsNfoNlfTu8_kcwzbIoZ7TzCm0Ku7.#e2bb4noreply@blogger.comtag:blogger.com,1999:blog-835341608950140555.post-84161809703449618082009-03-24T08:44:00.000+01:002009-03-24T08:44:00.000+01:00You are absolutely right. Thanks for the free pyth...You are absolutely right. Thanks for the free python lesson... Calling pow(1234,5678,90) is about 17 times faster than calling the above's modExp(1234,5678,90).<BR/><BR/>I actually wrote this entry thinking that, to compute the multiplicative inverse of a number modulo a prime number, it would be faster to use direct modular exponentiation than to use the extended euclidean algorithm. Well, it wasn't, but for a small factor, but I anyway discarded half the post and code I had written. I have now rechecked, and it seems my intuition was right, since at least for prime modulos smaller than ~50,000, if the modular exponentiation is done without any intermediate redundant function such as mine, direct exponentition is faster than Euclid's...<BR/><BR/>I'm going to have to do some recoding and testing, but your comment is definitely going to require redoing (extending) the entry on the modular multiplicative inverse, and may require extensive rework of the one on wheel factorization, which may also speed up considerably...<BR/><BR/>Thanks!Jaimehttp://www.blogger.com/profile/02831887559711602902noreply@blogger.comtag:blogger.com,1999:blog-835341608950140555.post-59416545334793805542009-03-24T04:14:00.000+01:002009-03-24T04:14:00.000+01:00Interesting article, and interesting blog which I ...Interesting article, and interesting blog which I look forward to reading more of.<BR/><BR/>However, correct me if I am wrong, but the functions described here are redundant for Python users.<BR/>Python has the function<BR/>pow(...)<BR/> pow(x, y[, z]) -> number<BR/><BR/>With two arguments, equivalent to x**y. With three arguments, equivalent to (x**y) % z, but may be more efficient (e.g. for longs).<BR/><BR/>which efficiently (in C) implements modular exponentiation.bwwsNfoNlfTu8_kcwzbIoZ7TzCm0Ku7.https://me.yahoo.com/a/bwwsNfoNlfTu8_kcwzbIoZ7TzCm0Ku7.#e2bb4noreply@blogger.comtag:blogger.com,1999:blog-835341608950140555.post-71413712753692623842009-03-21T02:44:00.000+01:002009-03-21T02:44:00.000+01:00I just wanted to throw out a word of appreciation....I just wanted to throw out a word of appreciation. The posts so far haven't been new information for me, but your code and writing are so lucid I feel I have a much better handle on these topics. I'm looking forward to future posts!bbblakerhttp://www.blogger.com/profile/15387744242923547745noreply@blogger.comtag:blogger.com,1999:blog-835341608950140555.post-47378162617155112302009-03-18T20:25:00.000+01:002009-03-18T20:25:00.000+01:00While I hope the code I write ends up being good e...While I hope the code I write ends up being good enough so that this blog can serve as a repository of algorithms, and truly be a numerical cookbook, the true purpose is to give some insight into why things are done the way they are done.<BR/><BR/>I haven't benchmarked them, but the code in the links you people have posted looks as if it should perform at least as good as the best I can produce. They all are much better than what this post holds, which is why it is titled "Prime Numbers the Wrong Way"...<BR/><BR/>I actually deal with some of the algorithms in Charles and Louis links in my new post:<BR/><BR/>http://numericalrecipes.blogspot.com/2009/03/prime-numbers-2-sieving-of-erathostenes.html<BR/><BR/>Primality testing, both in probabilistic and deterministic fashions, will have to wait a little longer, but will also find their way to these pages.<BR/><BR/>There is a great review on many of these subjects that can be found here as well:<BR/><BR/>http://krenzel.info/?p=83<BR/><BR/>In any case, thanks for commenting!Jaimehttp://www.blogger.com/profile/02831887559711602902noreply@blogger.comtag:blogger.com,1999:blog-835341608950140555.post-68487412157483948012009-03-18T20:12:00.000+01:002009-03-18T20:12:00.000+01:00Hope I won't dissapoint you...In the weeks to come...Hope I won't dissapoint you...<BR/><BR/>In the weeks to come I have the intention of dealing with prime numbers, FFTs, and then some algorithmic geometry, at least convex hulls and Voronoi diagrams...<BR/><BR/>And, of course staying away from those nasty libraries that take all the fun away!<BR/><BR/>Do feel free as well to leave your suggestions for topics you'd like to see worked out in detail.Jaimehttp://www.blogger.com/profile/02831887559711602902noreply@blogger.comtag:blogger.com,1999:blog-835341608950140555.post-66333634168009780292009-03-18T18:24:00.000+01:002009-03-18T18:24:00.000+01:00Here's really fast primality testing. Probabilisti...Here's really fast primality testing. Probabilistic, but good enough for all purposes and widely used:<BR/><BR/>http://eli.thegreenplace.net/2009/02/21/rabin-miller-primality-test-implementation/elibenhttp://getopenid.com/elibennoreply@blogger.comtag:blogger.com,1999:blog-835341608950140555.post-86981104126721859132009-03-18T13:27:00.000+01:002009-03-18T13:27:00.000+01:00Your resolution on not using any libraries has ear...Your resolution on not using any libraries has earned you a place in my "must come back and check" list. Good luck.sykorahttp://lucentbeing.myopenid.com/noreply@blogger.comtag:blogger.com,1999:blog-835341608950140555.post-84133776241108799162009-03-18T10:25:00.000+01:002009-03-18T10:25:00.000+01:00see also :http://code.activestate.com/recipes/5765...see also :<BR/>http://code.activestate.com/recipes/576596/Louishttp://www.blogger.com/profile/05339662769038811146noreply@blogger.comtag:blogger.com,1999:blog-835341608950140555.post-42282271184820363542009-03-18T05:01:00.000+01:002009-03-18T05:01:00.000+01:00Check out http://www.tiawichiresearch.com/?p=44 fo...Check out http://www.tiawichiresearch.com/?p=44 for testing the primality of a numberCharleshttp://www.blogger.com/profile/02642590751854772030noreply@blogger.comtag:blogger.com,1999:blog-835341608950140555.post-60034365350171223402009-03-18T01:05:00.000+01:002009-03-18T01:05:00.000+01:00Glad to discover you have a blog. I look forward t...Glad to discover you have a blog. I look forward to reading more.Johnhttp://www.blogger.com/profile/07480208135315956118noreply@blogger.com