Brian Mastenbrook scripsit: > It's a mistake to assume that operations on fixnums are O(1).
It's a mistake, for that matter, to think that operations on vectors are O(1), even if the vector is fully in RAM. It's just that the constant factors for vectors are so much smaller than those for lists (and lists get worse every year) that the "lists slow, vectors fast" model can safely persist. > I think there's a fair amount of incorrect assumptions about > arithmetic complexity floating around. The bottom line is that > multiplication is not O(1), nor is it O(n) in the number of bits in > the number. In principle, no. But CPU manufacturers have made fixed and floating addition and multiplication run in a roughly equal number of clock cycles, partly because of benchmarks that rewarded them for doing so. So that other old model, "fixnums fast, flonums slow" (except insofar as fixnums can be represented unboxed and flonums cannot) is now obsolete. -- John Cowan [email protected] http://www.ccil.org/~cowan Most people are much more ignorant about language than they are about [other subjects], but they reckon that because they can talk and read and write, their opinions about talking and reading and writing are as well informed as anybody's. And since I have DNA, I'm entitled to carry on at length about genetics without bothering to learn anything about it. Not. --Mark Liberman _______________________________________________ r6rs-discuss mailing list [email protected] http://lists.r6rs.org/cgi-bin/mailman/listinfo/r6rs-discuss
