April 2014 - mathfun@mailman.xmission.com

[math-fun] new language - anyone?
by Warren D Smith 20 Apr '14

20 Apr '14

Do you want to work on defining a new computer language? Send me email. -- Warren D. Smith

4 4

Re: [math-fun] bit-reverse
by Henry Baker 20 Apr '14

20 Apr '14

The important thing these days isn't _wires_ per se, but chip _area_, and # of wiring layers. Various shifts & reverse can easily be performed on n bits, but this typically requires O(n^2) chip area. Most ALU's do have such a shifter, but most don't have a bit reverser, which would probably cost another layer. At 08:04 AM 4/20/2014, Allan Wechsler wrote: >Doesn't it take _no_ gates to reverse a word, no matter how long it is? >Just a bunch of wires.

1 0

[math-fun] Shaders?
by Fred Lunnon 20 Apr '14

20 Apr '14

On 4/20/14, David Makin <makinmagic(a)tiscali.co.uk> wrote: > Personally the only coding I'm really interested in now is shader fragments > and for those interested who have a decent shader video card check > http://www.shadertoy.com/ (use Chrome, Safari or IE not Firefox). Under Mavericks: does not work with Safari; does work with Firefox! Now all I have to do is unscramble the jargon sufficiently to figure out what this is about ... WFL

1 0

[math-fun] bit-shift with skips
by Joerg Arndt 20 Apr '14

20 Apr '14

Recall the (IMHO very neat) method to generate the subsets of a given bitset (look at the methods next() and prev() ): class bit_subset // Generate all all subsets of bits of a given word. // // E.g. for the word ('.' printed for unset bits) // ...11.1. // these words are produced by subsequent next()-calls: // ......1. // ....1... // ....1.1. // ...1.... // ...1..1. // ...11... // ...11.1. // ........ // { protected: ulong U; // current subset ulong V; // the full set public: explicit bit_subset(ulong v) : U(0), V(v) { ; } ~bit_subset() { ; } ulong current() const { return U; } ulong full_set() const { return V; } ulong next() { U = (U - V) & V; return U; } ulong prev() { U = (U - 1) & V; return U; } ulong first(ulong v) { V=v; U=0; return U; } ulong first() { first(V); return U; } ulong last(ulong v) { V=v; U=v; return U; } ulong last() { last(V); return U; } ulong shift_left() { /* ?? what ?? */ } }; I ask you to fill in the shift_left() method. It shall do a left shift by one position as shown in the following examples: V ..........111111 <--= the full set U ..........111.11 <--= the subset we start with ..........11.11. ..........1.11.. ...........11... ..........11.... ..........1..... ................ (We always start with U the full set except for the third lowest bit.) V ....111111..1.1. U ....11111...1.1. ....1111.1..1... ....111.11...... ....11.11....... ....1.11........ .....11......... ....11.......... ....1........... ................ V ..1.1.111..11..1 U ..1.1.111...1..1 ..1.1.11...11... ..1.1.1.1..1.... ..1.1..11....... ..1...11........ ....1.1......... ..1.1........... ..1............. ................ V ..1.1.111...1.11 U ..1.1.111.....11 ..1.1.11....1.1. ..1.1.1.1...1... ..1.1..11....... ..1...11........ ....1.1......... ..1.1........... ..1............. ................ V ..1.1.111.....11 U ..1.1.11......11 ..1.1.1.1.....1. ..1.1..11....... ..1...11........ ....1.1......... ..1.1........... ..1............. ................ V ...1........1.1. U ............1.1. ...1........1... ...1............ ................ Your code shall be O(1). And awesome. Hint: start rewriting next() as ulong next() { U = (U + 1 + ~V) & V; return U; } This highlights that the gaps between the bits of U are filled with ones to let the addition(s) propagate. Spoiler below. Spoiler belowerer. Spoiler more belowerer. Shpoiler shtill belowerer, skrollen Sie schnell! ---------- SPOILER ---------- : ulong shift_left() { U = ( (U << 1) + ~V ) & V; return U; } Came up with that yesterday night only. Has anyone seen anything alike? The situation for ulong shift_right() { /* Try! Har, har, har! */ } is quite different, because we do not have the equivalent for bits propagating to the right. A revbin would (at least partially) mitigate the situation. Challenge: write a shift_right() (O(log(n)) is just fine!) that doesn't totally suck. I gave up on that. Best, jj

1 0

[math-fun] reverse binary in hardware
by Warren D Smith 20 Apr '14

20 Apr '14

It is trivial. We have hardware to perform "move register A to register B." Exact same hardware just with wiring changes, would do "...in reversed bit order." This would be about the simplest machine instruction to implement in hardware, simpler than essentially any other instruction.

1 0

Re: [math-fun] intel and bad instruction sets history/philosophy
by Henry Baker 19 Apr '14

19 Apr '14

I'm not going to defend C or any high-level language for not supporting add-with-carry, because I've argued for the same thing myself. I will try to give the traditional side of the argument, tho. The problem with add-with-carry is that the carry bit doesn't fit into the standard syntactical model, so you can no longer use the infix "+" operator. This isn't a problem for Lisp, because Lisp never believed in infix operators in the first place, but it is a huge problem for most other "high level" languages that attempt to utilize infix notations. But even more difficult is the carry _out_ bit (or the high order portion of a single-single multiply operation. By rights, this operation produces _two_ results, and again most "high level" languages don't want to deal with that. Common Lisp follows the Lisp Machine (and Forth-like stack languages) in offering _multiple_ return values. The Common Lisp syntax is unfortunately quite awkward: (multiple-value-bind (low high) (dpmultiply x y) ... do something with 'low' and 'high' ...) I would have preferred something more like: (let ((low high (dpmultiply x y))) ... do something with 'low' and 'high' ...) So it is quite easy to fit add-with-carry, double-precision-multiply, etc., into a Lisp language. If you understand so-called "continuation-passing style" (CPS), then you can do a lot better, and no longer have to rely on a stack: (dpmultiply x y #'(lambda (low high) ... do something with 'low' and 'high' ... )) "dpmultiply" multiplies x*y and then (tail) _calls_ the "continuation" function with the low & high portions. (C languages sometimes calls this type of function argument a "call-back", which is a bit tortured, and also doesn't work very well in C due to C's lack of proper closures.) Believe it or not, with proper type declarations (and/or good type inferencing capabilities) these Lisp expressions can be compiled into essentially optimal assembly code for fixed-precision arithmetic (often called "FIXNUMs"). So a Lisp-like language can be compiled to machine code every bit as good as any C compiler. Hopefully, we'll turn Warren into a Lisper, yet! At 06:33 PM 4/19/2014, Warren D Smith wrote: >What about "add with carry"? Sorry, C pretends that does not exist and so >if you want to write multiprecision arithmetic, you cannot use C (unless willing to pay >heavy performance price) and must put in some assembler. > >All because, the providers of C, *SUCKED.* And practically every high-level language >in the universe, pretends add-with-carry does not exist. >It is just appalling. What is their problem?

1 0

Re: [math-fun] math-fun Digest, Vol 134, Issue 40
by Warren D Smith 19 Apr '14

19 Apr '14

Hah! Knuth has 8x8 bit-matrix instructions in MMIX! Well, a lot of people, including me, have been saying for a long time instructions sets sucked in some easily-improvable ways. Let's hope Knuth gets listened to. He's trying harder than most of the whiners. Thing is, I think Intel actually KNOWS they've painted themselves into a corner with a fundamentally bad architecture, but they did an experiment where they tried to make+sell a better one and nobody bought it since their old x86 software would not work on it. The lesson they learned was: to hell with good architecture, the only thing that matters is backwards compatibility back to the stone age. And I think to a considerable extent the same is true with computer languages. The amount of wasted effort that has gone into creating better languages which then do not achieve commercial success and high use, is tremendous. (And human languages too, e.g. why are we not speaking Esperanto?) -- Warren D. Smith http://RangeVoting.org

3 2

Re: [math-fun] bad architectures
by Henry Baker 19 Apr '14

19 Apr '14

Actually, the blame should fall on IBM, not on Intel. IBM chose Intel 8086 for its PC _precisely because_ the 8086 was a bad architecture -- in particular, an architecture that would have trouble growing beyond 16 bits. IBM did this to avoid any competition with its 32-bit & beyond mainframes. Later on, IBM dabbled a bit with so-called "RISC" architectures, but never really had their hearts in it, so they never amounted to very much. IBM also developed "micro mainframes" that were inexpensive ways to run standard mainframe software, but these were never marketed aggressively, and may have been built simply as "spec-ware" or RFP-ware, and not really available for an ordinary customer to purchase. Intel experimented with a wide variety of weird architectures (thank you, Justin Rattner) that wasted huge amounts of research dollars (a lot of which came from Uncle Sam) but never amounted to anything. It wasn't until AMD became a real threat with its 64-bit ideas that Intel was finally forced to start getting its act together. Many govt labs bought AMD machines with great abandon, and given the small size of AMD relative to Intel, I'd look very carefully at the AMD architecture & its masks for "hidden" instructions and instruction modes that AMD might have developed for its best customers. AMD's integrated GPU's were a good idea for the ordinary consumer computer games, but even a better idea for one-way function hacking like bitcoin mining and password cracking. Re backwards compatibility: that may be true for the Microsoft kingdom, but the success of the ARM architectures in phones & Linux shows that assembly-level compatibility no longer has the importance that it once had. At 03:55 PM 4/19/2014, Warren D Smith wrote: >Thing is, I think Intel actually KNOWS they've painted themselves into >a corner with a fundamentally bad architecture, but they did an >experiment where they tried to make+sell a better one and nobody >bought it since their old x86 software would not work on it. >The lesson they learned was: to hell with good architecture, the only thing >that matters is backwards compatibility back to the stone age.

1 0

[math-fun] winding points and sphere handles
by Fred Lunnon 19 Apr '14

19 Apr '14

This material is surely elementary, but I couldn't find it anywhere: maybe someone can cite a reference? A 2-sheet Riemann sphere with 2 winding points is homeomorphic to a torus: for if its tube radius remains fixed while the swept radius approaches zero, the torus approaches a double sphere with winding points at opposite ends of a diameter --- whence they may be deformed to arbitrary locations, and the sphere to a topological sphere. In a similar fashion, s sheets with t winding points are homeomorphic to a sphere with (s t)/4 handles, ie. genus = (s t)/4 , at any rate for s, t even; otherwise it perhaps suffices to take the ceiling ... I would probably have remained unaware of this idea if I had not once been experimenting with a simple Maple graphics demo program to plot a torus, and noticed that what I had casually assumed must be a simple sphere instead appeared mysteriously fuzzy and uneven. On this occasion at any rate, Maple was innocent of blame, and indeed had provided valuable insight! Fred Lunnon

2 3

[math-fun] bitboard dihedral group (crazy hackers please?)
by Warren D Smith 19 Apr '14

19 Apr '14

Since mathfunners have impressed me with their crazy-bit-twiddling capabilities, here's a challenge. In chess programming, they often employ 8x8 "bitboards" -- i.e. 64-bit machine words. A bitboard question which I think has never been fully answered, is this. There are 8 ways, given a 8x8 chessboard, to rotate and flip it (dihedral group D4). For each of the 7 non-identity ways, find the fastest algorithm you can that performs that bit-permutation on a 64-bit word. Henry Warren's book "Hacker's delight" already discussed the 8x8 matrix transpose, which is one of these 7 problems. He ended up with the following incredible algorithm: uint64 TransposeBitBd(BitBd x){ //Adapted from Warren:: Hacker's delight. uint64 t; t = (x ^ (x >> 7)) & U64(0x00AA00AA00AA00AA); x = x ^ t ^ (t << 7); t = (x ^ (x >> 14)) & U64(0x0000CCCC0000CCCC); x = x ^ t ^ (t << 14); t = (x ^ (x >> 28)) & U64(0x00000000F0F0F0F0); x = x ^ t ^ (t << 28); return(x); } Good luck figuring it out. Another pointed out by Jorg Arndt is: the single machine instruction "bswap" (on many processors) is available which permutes the 8 bytes into reverse order -- this causes the board to flip vertically (or horizontally, depending how you'd ordered its bits in a raster). Another (180 degree board rotate) is the bit-reversal permutation, for which an extremely fast and mysterious algorithm is given by Don Knuth and you can go even faster on machines with bswap, we discussed this problem in earlier posts. For 90 and 270 degree board rotations with or without accompanying flips, I can do it in O(N) operations on an NxN bitboard in various fairly obvious ways that involve multiplications and maskings. Is it possible to achieve o(N) somehow? If the squares of the board were numbered 0..63 in a peculiar manner, e.g. the top left quadrant is numbered 0..15 then the other quadrants are numbered 16..31, 32..47, 48..63 in symmetric (rotated) ways, then you could perform a 90, 180, or 270 degree rotation trivially by simply doing a single circular-shift-by-16 (32, 48) hops on the 64-bit word. Probably this strange kind of numbering would be unfriendly for most computer chess purposes (?), but for this purpose it's great. More precisely, I believe there is an ordering of the 64 chessboard squares 0..63 (and there are sub-orderings of the 4x4 board 0..15 and 2x2 board 0..3) with these properties: 90 rotate: add 16 mod 64, aka circular shift by 16 180 rotate: add 32 mod 64 270 rotate: subtract 16 mod 64 For the 4x4: 90 rotate: add 4 mod 16, aka circular shift by 4 180 rotate: add 8 mod 16 270 rotate: subtract 4 mod 16 For the 2x2 where the ordering is 32 01: 90 rotate: add 1 mod 4, aka circular shift by 1 180 rotate: add 2 mod 4 270 rotate: subtract 1 mod 4 flip horizontally: XOR with 01 flip vertically: XOR with 11 And back on the full 8x8: flip board: permute the four 16-bit subwords as ABCD -> BADC or ABCD -> CDAB, and then within each 16-bit subword, perform a 4x4 flip. This in turn is accomplished recursively by the same operation on its four 4-bit subwords, then within each do a 2x2 flip as described above. So, my head is hurting, but it seems as though by means of this kind of numbering scheme, it becomes possible on an NxN bitboard (N=power of 2) to implement the 4 rotation operations in O(1) steps each, and the flip operation in O(logN) steps. I'll only believe the latter when I see more details, so for now regard this as a sketch/conjecture. It might be you cannot "parallelize" it and hence cannot achieve logN, instead getting something sadder like N or sqrt(N) steps. Anyhow, the original dihedral-7 problem is clearly not a triviality. -- Warren D. Smith http://RangeVoting.org

4 4