Thursday, April 27, 2017

NASA at...

NASA at ... its most awesome, and at its least awesome...  Too bad there's so much more of the latter than the former...

Paradise ponders: artichokes, kits, better indexes, and electricity edition...

Paradise ponders: artichokes, kits, better indexes, and electricity edition...  Yesterday Debbie made a new dish – a casserole of chicken, artichokes, onions, Parmesan cheese, and mayonnaise.  That's her serving at right, over rice.  This one is a keeper, and I was a bit surprised just how tasty those artichokes were.  They were canned, in water, not the marinated kind I'm familiar with.  The water was salted, so we leached as much as possible out by soaking them in fresh water, replaced several times, and that seemed to work very well.  A keeper recipe for sure!  Both of us thought of several modifications we could make to it that might be even better.  I sense some artichokely experimentation in our future...

Over the past few days some tools I've ordered arrived: a couple of jigs (for making box joints and mortise-and-tenon joints) and a router table.  All three of these are kits – boxes of parts with bags of nuts and bolts.  Big bags of nuts and bolts.  I'm gonna be putting things together for a while before I can use them.  All three of these were long-planned, but I need them now to let me build some stuff for the cattery.  Somehow I didn't expect the jigs to be kits, but the fact that the router table is a kit doesn't really surprise me...

A couple days ago I posted about an index to look up the value of the largest decimal digit that is smaller than a given binary value.  The code that I posted was ... not optimal.  Here's a better attempt:
int lz = Long.numberOfLeadingZeros( _val );
int mag = 63 - lz;
int hi = mag << 3;
long sec = Long.highestOneBit( _val ) ^ _val;
int lo = (int)(sec >>> Math.max(0, mag - 3));
int index = hi | lo;
In addition to a better algorithm, I also made the code easier to read. The compiler optimizes the local variables away, so there's no performance impact to this.  The 9 bit index generated is pretty simple.  If 2^k is the most significant bit in _val, then the upper six bits of the index are k, and the lower three bits are the bits in _val at 2^k-1, 2^k-2, and 2^k-3 (with a bit of special casing for k < 3).

I'm going to be putting up a little shed soon, to house some components of our sprinkler system.  I had my favorite electrician (Tyler, from Golden Spike Electric) out yesterday evening to check out the job.  It's such a pleasure to work with people like him!  I want something kind of weird (naturally!), and he had absolutely no problem accommodating me.  I'm going to have him run a 50 amp 220 volt circuit to a subpanel in the new shed, and I'm going to wire it from there.  “No problem”, says he – and we looked over the existing panel that he'd connect to.  There was a circuit installed long ago that ran to an external plug for an RV.  This is not something we'll ever need, so we're going to remove that and steal the existing breaker (which happens to be 50 amp!) for my new subpanel.  Easy peasy!

Wednesday, April 26, 2017

Paradise ponders: Debbie's “graduation”, filling station milestone, steam train, and tax cuts...

Paradise ponders: Debbie's “graduation”, filling station milestone, steam train, and tax cuts...  This morning Debbie went in to see her surgeon for a two week post-surgery followup.  He pronounced her recovery to be great, ready to get her staples taken out, and cleared for any physical activity that didn't cause her pain.  She looked so good, in fact, that he declared it unnecessary for her to have the usual subsequent followup visits.  This prompted a nurse who was in the room to comment that Debbie had “graduated”.  Yay!  The staples came out (something that Debbie really hates – she crushed my hand and buried her head in my shoulder while the nurse did this), and now her big job is to see how far she can push herself with exercise before it gets painful.  First milestone there will be walking without any walker, crutches, or cane.  The surgeon said she could be doing this just as soon as she can comfortably put full weight on her left knee.

Yesterday the guys were here working on our filling station.  They got all the pipe cut, threaded, and installed – the tanks are now actually connected to the nozzles!  I just put in a call to my fuel supplier, and within a few days I should actually have some gasoline and diesel fuel sloshing around in those  tanks.  There's still more work to do on the filling station, but we can use it while that work gets done.  I've just ordered the steel door to go in the front of it; that should be here in six weeks or so.  I've also got Randy Bingham (the mason who did our fireplace) lined up to put rock on top and all around it, but it might be a while before that gets done.  Progress! 

Yesterday we'd planned to go see a steam locomotive that was scheduled to stop for just a half hour in Cache Valley.  The place where it was to stop was the teensy little town of Cache Junction, just south of my brother Scott's home.  This town has about four houses, and it's kind of in the boonies of Cache Valley – so we weren't expecting many people to show up for it.  Man, were we wrong!  There were a couple hundred cars parked there, overflowing the little parking area to line the sides of the roads for a half mile or so on both sides of town.  I'd guess that around a thousand people were milling all about.  In that environment there was no way for us to park close by for a view of the train, and Debbie's not ready to walk over rough ground, so we just drove through town and marveled at the size of the crowd.  We visited for a little while with my brother (where we picked up some beautiful logs he'd saved for me) and on the way out we did get to see the locomotive as it approached Cache Junction.  We crossed the tracks about 2 miles from Cache Junction and were amused to see that a crowd had gathered there as well.  This steam locomotive was darned popular here!

As I started writing this post, news is trickling in about Trump's proposed tax cut.  I have no idea what the chances are that this will actually get through Congress intact, but I'm skeptical given the magnitude of the cuts and the general hostility of the Democrats.  But one aspect of the proposed plan jumped out at me: repealing the federal income tax deduction for state and local taxes.  This deduction is, in effect, a federal subsidy that disproportionately benefits residents of high tax states.  I'd be delighted to see that actually be repealed, but it's easy to foresee that the Democrats will start crazed howling about this one.  That's so obvious that I have to wonder if it was included in the proposal mainly as a sop whose removal could be traded for Democratic votes in the Senate...

Tuesday, April 25, 2017

Binary to decimal conversion performance...

Binary to decimal conversion performance...  Now here's an obscure topic that I've worked on a great many times over my career.  The original inspiration for me to work on this came from programming the Z-80, way back in the '70s.  That little 8 bit microprocessor could do 16 bit addition, but it had no multiply or divide instructions at all.  Often the application I was working on needed higher precision math (usually 32 bits), so I had a library of assembly language subroutines that could do the basic four 32 bit operations: add, subtract, multiply, and divided.  Multiply and divide were maddeningly slow.  Eventually I came up with a way to speed up multiply considerably, but divide was intractably slow.

This slow divide performance was on full display anytime I wanted to convert a 32 bit binary integer to its decimal equivalent.  The canonical algorithm uses repeated division-with-remainder by ten.  For instance, to convert the binary number 11001001 to its decimal equivalent, you would do this:
11001001 / 1010 = 10100 remainder 1
10100 / 1010 = 10 remainder 0
10 / 1010 = 0 remainder 10
The result is then the remainders, in decimal, in reverse order: 201.  You need one division operation for each digit of the result.  A 32 bit number might have as many as ten digits, and on that low-horsepower little Z-80, those divisions were really expensive.  So I worked hard to come up with an alternative means of conversion that didn't require division.

What I came up with has been independently invented by many people; I wasn't the first, I'm sure, and I don't know who was.  The basic technique depends on a simple observation: there aren't all that many possible decimal digits whose value fits in a given length binary number.  For instance, in a signed 32 bit binary number, the largest positive decimal number that can be represented is 2,147,483,647.  That's 10 decimal digits, any of which can have the non-zero values [1..9], except the most significant one can only be [1..2].  That's just 83 values.  If you pre-compute all those 83 values and put them in a table, then you can convert a binary number to decimal with this algorithm:
start with the binary value to be converted
while remaining value is nonzero
    find the largest value of a decimal digit < the remaining value
    record the digit
    subtract that decimal digit value from the remaining value
This produces the decimal digits in order, from the most significant digit to the least significant digit.  Most importantly, it does so with no division required.

That was vital to getting decent performance out of that Z-80.  But what about a modern processor?  Well, it turns out that in relative terms, division is still the red-haired stepchild of CPU performance.  On a modern Intel or ARM processor, 64 bit integer division can take over 100 CPU clock cycles.  Multiply operations, by comparison, take just a handful of clock cycles, while addition and subtraction are generally just 1 or 2 clock cycles.  Even when using a high-level language like Java, algorithms that avoid using division repetitively can still produce large performance gains.  I've done this five or six times now, most recently to get a 6:1 performance gain when converting floating point values to XML.

One line of the above algorithm I sort of glossed over: the bit about finding the largest value of a decimal digit that is less than the remaining value.  The naive way to do this would be to use a linear search, or possibly a binary search of the table of decimal digit values.  This would require a number of iterations over the search algorithm, at best an average of 4 iterations for a binary search over a table big enough for 32 bit values.  For 64 bit values we'd have 171 decimal digit values, and we'd need 5 iterations for that binary search.

We can do better, though, by taking advantage of the fact that there's a close relationship between the binary values and the largest fitting decimal digit.  I just finished coding up a nice solution for finding the largest decimal digit that fits into a signed 64 bit integer.  It works by using a table with 512 entries, about three times as many as we have possible decimal digit values.  Given a 64 bit positive binary number, the Java code that computes the index into that table is:
int lz = Long.numberOfLeadingZeros( value );
int index = ((63 - lz) << 3) + (0xf & (int)Long.rotateRight( value, 60 - lz));
Pretty simple code, really. It's also very fast.  Best of all, with a properly constructed table the index will point to an entry that will either be the correct one (that is, the largest decimal digit that will fit into the value) or it will be too big.  If it is too big, then the preceding entry in the table is guaranteed to be the correct one.  Much better than the iterative searches!

With those two techniques in combination, I'm doing conversions from binary to decimal with no divisions and no iterative searching.  It's very challenging to benchmark performance in Java, but my simple testing shows about 5:1 improvement in performance for random numbers in the 64 bit positive integer range.  Smaller numbers (with fewer decimal digits) show smaller performance gains, but always at least 2:1.  I'll call that a win!

Monday, April 24, 2017

Paradise ponders: rain, and strange coincidences edition...

Paradise ponders: rain, and strange coincidences edition...  It is pouring on us right now (see the radar snapshot at right).  I'm up in my barn office, and the noise of the rain hitting the steel roof over my head is deafening.

This morning I spoke for a little while with the attorney I'm using to handle a real estate transaction in Virginia.  He mentioned that he was a little familiar with Utah, as he used to come out here for vacations, especially near Moab.  So I shared a bit with him about our numerous trips there, and I mentioned that we knew the La Sal Mountains very well.  He then related his happy visits to Pack Creek Ranch, a now-defunct resort on the western slopes of the La Sals.  Debbie and I have very happy memories of that place, having stayed there several times ourselves.  It's a little bitty resort, way out of the way, exactly our sort of place precisely because it's not very popular.  And yet ... this lawyer from Virginia knew it, and had stayed there three or four times.  What a bizarre coincidence!

A step taken...

A step taken...  This morning I registered a new domain:  I was a bit surprised that it hadn't already been taken – my usual experience with finding domain names is that the first 1,000 or so that I try have already been snagged. :)  Further, to my amazement, 60 seconds after registering, the DNS resolution was already working.  The first domain I ever registered (, back in '93) took several days to get that far.

This new registration is a first step for an open source project I'm going to start working on.  The main purpose is to actually implement the observations and ideas I've had for representing money in Java.  The vast majority of that work lies in representing high precision decimal numbers, hence the domain name.  I won't have any web site for at first; I locked down the name mainly so I could safely use it for Java class names...

Sunday, April 23, 2017

Paradise ponders, 8' lumber, oven removal, and scallops edition...

Paradise ponders, 8' lumber, oven removal, and scallops edition...  Tomorrow we're supposed to get our new oven installed.  You may remember that we gave up on our old oven after three failed attempts to get it repaired.  The new one is a Bosch model that we're hoping we're just as happy with as we are with our Bosch dishwasher.  Also, it came highly recommended by our repair technician.

So this morning I tackled what I thought was likely to be an all-day job: removing the old oven and installing an electrical junction box.  The house's previous owner had done an awesomely shabby job of wiring the old oven: he just used wire nuts to join the wires, covering them with approximately eight miles of electrical tape.  It's the sort of electrical job you might imagine a child doing.  I ran into something similar when I replaced the microwave directly above this oven, and there I had room to install a standard outlet box.  The new oven is 220V, and those outlets are way too big to install in the cramped space the oven must fit in.  So I went with a hard-wired junction box.

Taking the oven out turned out to be relatively easy.  I had the old oven out in our garage just a half hour after starting.  With some creative use of our hand truck, it wasn't even all that difficult.  The hardest part was getting it onto the hand truck – wrangling 185 lbs of oven by myself was a bit of a challenge!  But I got it...

We made a run to Home Depot and got all the electrical parts I needed.  Installing them took all of another half hour.  So by 10 am I was completely done with that job.  Yay!

So we made another run to Home Depot, this time to buy the stuff I needed to build out a couple of frames around two of our basement windows in our cattery.  These are the windows that we've opened up to our sun room.  I removed the glass sliding windows, including their frame, and now we just have the steel frame that's set into the basement's concrete wall.  I'm building a frame out of cedar 1x8's with the boards perpendicular to the plane of the old window.  This is at the suggestion of our mason, who will use that frame as one edge of the rock he's installing.

I needed to buy five 8' long pieces of cedar (1x8s), so I did some measuring to see if it would be possible to fit those in our Model X.  To my surprise, the answer was yes!  About six inches of the boards needed to extend over the center console, which I covered with a shipping pad to protect.  The photo at right I took while standing behind the open rear hatch.  You can see the “hole” between the two front seats where we stowed the boards, along with the pads I used to protect it.  We keep getting surprised by what we can carry in the Model X – it's really quite roomy inside (especially our five seat version with the rear seats folded down).

On the way to Home Depot, I stopped for a few groceries at Smith's.  That's not where we usually shop, so while I was in there I did a little scouting.  On the way by the seafood counter I spotted scallops – the great, big sea scallops that Debbie uses in her scrumptious baked scallops recipe.  I bought a pound and a half, and Debbie is cooking them as I write this.  Feast today!