There's been a fair bit of discussion over at Reddit about this blog post: https://blog.svpino.com/2015/05/07/five-programming-problems-every-software-engineer-should-be-able-to-solve-in-less-than-1-hour

To clarify one point right from the start: The author said that he expects applicants to be able to solve all five problems in a single hour. Not one hour per problem; all five problems in the same hour. (He also (much more than an hour) later posted a solution for problem #4 that was incorrect, much to the hilarity of /r/programming/.)

Problems 1 and 2 are trivial, I agree that anyone who wants to get their paycheck from programming should be able to do those in their favorite language in less than an hour very easily. (I didn't time myself on those, but I'm sure I came in under 15 mins to solve the pair.)

Problems 4 and 5 are tougher. With problem #4 you can probably get away with using a brute-force solution, and the resulting program will still run quickly enough. So in that way you can probably solve problems 1-4 in an hour. (Though depending on programming language traps - see below.)

Problem 5 is much, much tougher. Personally, I don't think I would have even gotten started on problem 5 within the hour. My personal opinion is that the inclusion of problem #5 in the same hour as problems #1-4 invalidates this test.


But I actually don't want to talk about problem 5, or even problem 4. I want to talk about problem 3, the Fibonacci one. I think Reddit adequately covered problems 4 and 5. Problem 3 on the other hand wasn't talked about much, and can be either briefly interesting or really goddamn annoying depending on the language you use.

My first crack at problem 3 was a naive solution in C (gcc 4.2.7, x86) using long long ints. The last five or so Fibonacci numbers that version of the program spit out were way off. So at that point I went and typed lg(218922995834555169026) (log base 2 of the 100th Fibonacci number) into Google and got lg(218 922 995 834 555 169 026) = 67.5689854. So it would take at least 68 bits to (correctly) represent the 100th Fibonacci number.

The C standard is flexible about how many bits are allowed to be in an int, long int, long long int, etc - the ony rule is that the larger data types must have at least as much storage as the smaller ones. I wonder how many bits are in a long long with my particular compiler?

owl:~/fiveproblems> cat sizeof-longlong.c
#include <stdio.h>

int main(void)
{
        printf("sizeof(long long int) = %zu\n", sizeof(long long int));
        return 0;
}
owl:~/fiveproblems> gcc -Wall -Wextra -pedantic sizeof-longlong.c
owl:~/fiveproblems> ./a.out
sizeof(long long int) = 8
owl:~/fiveproblems> 

Well, there's your problem! long long is only 8 bytes aka 64 bits. It can't accurately represent a 68 bit integer.

(This is probably obvious, but the "%zu" format specifier for printf() is a special GCC thing to allow you to easily print out size_t types (what sizeof() returns) without casting them to something else. This isn't very portable across architectures or compilers. But since I only wanted to know how may bits in a long long on this specific compiler and architecture, that's OK.)


Now that I was certain a long long int wouldn't work, I wondered if a floating-point representation might help. It might not get the answer precisely down to the 17th decimal place, but I thought maybe the results would be correct if they were rounded to the nearest integer. Wikipedia said that long double was usually an 80 bit extended precision type on x86 GCC, so it looked like it was worth a try, in spite of the fact that the mantissa in an 80-bit extended precision is only 63 bits long. So I quickly changed the program to use long doubles instead. When I ran this version of the program the last few numbers were much closer, but still not right:

#include <stdio.h>


int main(int argc, char **argv)
{
        int i;
        long double fibs[100];

        fibs[0] = 0L;
        fibs[1] = 1L;

        for(i = 2; i < 100; i++)
        {
                fibs[i] = fibs[i-1] + fibs[i-2];
        }

        printf("First 100 Fibonacci numbers =\n");
        for(i=0; i < 100; i++)
        {
                printf("%.0Lf\n ", fibs[i]);
        }
        printf("\n");

        return 0;
}
owl:~/fiveproblems> gcc -Wall -Wextra -pedantic fibs-longdouble.c
fibs-longdouble.c: In function ‘main’:
fibs-longdouble.c:4:14: warning: unused parameter ‘argc’ [-Wunused-parameter]
fibs-longdouble.c:4:27: warning: unused parameter ‘argv’ [-Wunused-parameter]
owl:~/fiveproblems> ./a.out
First 100 Fibonacci numbers =
0
 1
 1
 2
 3
 5
 8
 13
 21
 34
 55
 89
 144
 233
 377
 610
 987
 1597
 2584
 4181
 6765
 10946
 17711
 28657
 46368
 75025
 121393
 196418
 317811
 514229
 832040
 1346269
 2178309
 3524578
 5702887
 9227465
 14930352
 24157817
 39088169
 63245986
 102334155
 165580141
 267914296
 433494437
 701408733
 1134903170
 1836311903
 2971215073
 4807526976
 7778742049
 12586269025
 20365011074
 32951280099
 53316291173
 86267571272
 139583862445
 225851433717
 365435296162
 591286729879
 956722026041
 1548008755920
 2504730781961
 4052739537881
 6557470319842
 10610209857723
 17167680177565
 27777890035288
 44945570212853
 72723460248141
 117669030460994
 190392490709135
 308061521170129
 498454011879264
 806515533049393
 1304969544928657
 2111485077978050
 3416454622906707
 5527939700884757
 8944394323791464
 14472334024676221
 23416728348467685
 37889062373143906
 61305790721611591
 99194853094755497
 160500643816367088
 259695496911122585
 420196140727489673
 679891637638612258
 1100087778366101931
 1779979416004714189
 2880067194370816120
 4660046610375530309
 7540113804746346429
 12200160415121876738
 19740274219868223168
 31940434634990099906
 51680708854858323072
 83621143489848422976
 135301852344706746048
 218922995834555169024

owl:~/fiveproblems>

So now, I was kinda stuck. I knew that long double wasn't going to do it either. I wasn't about to write my own BigNum library, time was critical here. I had heard about some new, not very standard thing with 128 bit ints, so I went Googling, and found this:

http://stackoverflow.com/questions/11656241/how-to-print-uint128-t-number-using-gcc

Two things you should take away from reading that:

1. GCC (with -std=c99) does support a 128 bit integer, __int128 (or unsigned __int128 if you prefer).
   
2. GCC does not have a printf() format specifier for printing out 128 bit integers! You will have to write your own function to print out 128 bit ints!
   

(As an aside, let me say: the second item is total bullshit. I can't believe the people maintaining GNU libc would put a __int128 type into the language but NOT give you a way to print it out. The entire reason computers were invented was so they could do the math for us and tell us the answer, instead of having to do it ourselves!

"Well it's open-source, why don't you contribute and fix it?" Because my time has value. This whole discussion started with a set of five problems that had to be solved within an hour. If I have to spend weeks REWRITING THE GODDAMN COMPILER AND STANDARD LIBRARY then I've already failed.

Yes, GMP is a thing. And, hallelujah, it even comes with routines to print out the numbers it manipulates! But I shouldn't have to resort to that when there's an __int128 in the standard library.

Did I just choose the wrong language, trying to use C for large integers? Quite possibly so. Those of you who write code in Java probably know that Java has a BigInteger class that does arbitrary precision integers. Is C so crusty and ancient and badly curated that it's time to abandon it for Java? Because if so, I will. I would prefer to keep C as my go-to language. But if it's gonna ultra-fail on the simplest of things, like printing out an integer...)

So, finally, here's what ended up working (print_u128() function shamelessly copied from that StackOverflow page above):

owl:~/fiveproblems> cat fibs.c
#include <stdio.h>
#include <inttypes.h>
#include <stdint.h>


typedef unsigned __int128 uint128_t;

/*      UINT64_MAX 18446744073709551615ULL */
#define P10_UINT64 10000000000000000000ULL   /* 19 zeroes */
#define E10_UINT64 19

#define STRINGIZER(x)   # x
#define TO_STRING(x)    STRINGIZER(x)

static int print_u128(uint128_t u128)
{
    int rc;
    if (u128 > UINT64_MAX)
    {
        uint128_t leading  = u128 / P10_UINT64;
        uint64_t  trailing = u128 % P10_UINT64;
        rc = print_u128(leading);
        rc += printf("%." TO_STRING(E10_UINT64) PRIu64, trailing);
    }
    else
    {
        uint64_t u64 = u128;
        rc = printf("%" PRIu64, u64);
    }
    return rc;
}


// A GCC-specific trick to silence "unused variable" warns w/"-Wall -Wextra".
#define DIABLE_WARN_UNUSED __attribute__((unused))

int main(int DIABLE_WARN_UNUSED argc, char DIABLE_WARN_UNUSED **argv)
{
        int i;
        uint128_t fibs[100];

        fibs[0] = (uint128_t)0;
        fibs[1] = (uint128_t)1;

        for(i = 2; i < 100; i++)
        {
                fibs[i] = fibs[i-1] + fibs[i-2];
        }

        printf("First 100 Fibonacci numbers =\n");
        for(i=0; i < 100; i++)
        {
                print_u128(fibs[i]);
                printf("\n");
        }

        return 0;
}
owl:~/fiveproblems>
owl:~/fiveproblems> gcc -std=c99 -Wall -Wextra -pedantic fibs.c
fibs.c:6:18: warning: ISO C does not support ‘__int128’ type [-pedantic]
owl:~/fiveproblems>
owl:~/fiveproblems> ./a.out
First 100 Fibonacci numbers =
0
1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765
10946
17711
28657
46368
75025
121393
196418
317811
514229
832040
1346269
2178309
3524578
5702887
9227465
14930352
24157817
39088169
63245986
102334155
165580141
267914296
433494437
701408733
1134903170
1836311903
2971215073
4807526976
7778742049
12586269025
20365011074
32951280099
53316291173
86267571272
139583862445
225851433717
365435296162
591286729879
956722026041
1548008755920
2504730781961
4052739537881
6557470319842
10610209857723
17167680177565
27777890035288
44945570212853
72723460248141
117669030460994
190392490709135
308061521170129
498454011879264
806515533049393
1304969544928657
2111485077978050
3416454622906707
5527939700884757
8944394323791464
14472334024676221
23416728348467685
37889062373143906
61305790721611591
99194853094755497
160500643816367088
259695496911122585
420196140727489673
679891637638612258
1100087778366101931
1779979416004714189
2880067194370816120
4660046610375530309
7540113804746346429
12200160415121876738
19740274219868223167
31940434634990099905
51680708854858323072
83621143489848422977
135301852344706746049
218922995834555169026
owl:~/fiveproblems>

And for the record: pulling all the teeth and kicking all the dead whales down the beach that I had to, in order to make this program work, ended up taking two to three hours. So clearly, I'm not worthy to be a programmer. :P

Love the interactive map of the chip!

http://www.righto.com/2014/09/reverse-engineering-counterfeit-7805.html

That is really cool. I suspect the opto he used had a Schmitt trigger output. The circuit would work even better with a true analog output opto...

http://www.youtube.com/watch?v=ta7nlkI5K5g

I didn't think my respect for Jim Williams could get any higher. This, however... this is the nuclear option. I am literally in awe. I have seen the face of my god, and it is Jim.



"The extremely high resolution of this scale requires filtering to produce useful results. Very slight body movement acting on the platform can cause significant noise in A3’s output. This is dramatically apparent in Figure 12’s tracings. The total force on the platform is equal to gravity pulling on the body (the “weight”) plus any additional accelerations within or acting upon the body. Figure 12 (Trace B) clearly shows that each time the heart pumps, the acceleration due to the blood (mass) moving in the arteries shows up as “weight”. To prove this, the subject gets off the scale and runs in place for 15 seconds. When the subject returns to the platform the heart should work harder. Trace A confirms this nicely. The exercise causes the heart to work harder, forcing a greater acceleration-per-stroke."

http://www.linear.com/docs/4134

You know that typical game-show or quiz-bowl buzzer system, where each contestant gets a button and the first to press it is allowed to answer the question the host asked?

Someone asked for a circuit to implement such a system. I have dim memories of seeing designs for such systems in the distant past, but nothing I could remember clearly. So I decided to design my own.

( Read more...Collapse )

A Boulder Weekly article about her book:

http://www.boulderweekly.com/article-11529-who-died-at-crooked-creek.html

Say you're trying to use a computer to factor a number, N. N is large and you want to stop as soon as possible in the case that it's a prime.

If you don't have a lot of memory to work with, then the obvious thing is some kind of optimized trial division. (Which is not the same as - and not to be confused with - the Sieve of Eratosthenes. SoE has a lower time complexity, but requires far more space.)

The first key point about such trial division algorithms is that you should never divide by an even number other than 2. The reasoning for this is, I hope, obvious. In short, after trying to divide N by 2, thereafter only try dividing by odd numbers. (Of course in theory we would like to try only dividing by primes. But if we're in a space constrained situation, we probably don't have a list of all primes between 0 and N sitting around.)

The second key point about trial division algorithms is that they need to stop trying possible factors when they reach sqrt(N). If you've tried every (odd) number up to sqrt(N), and N isn't evenly divisible by any of them, then give up: N is prime.

You can compute sqrt(N) outright, but honestly I wouldn't even do that. Some compilers/languages have an isqrt(N) built-in that gives you the nearest integer larger than, or equal to, sqrt(N). This is exactly what you want. In addition, most isqrt()s are constant run time. (It's usually a small constant, even.)

If for some bizarre reason you don't have isqrt(n), you can synthesize it by using Newton-Rapheson (see Wikipedia page on isqrt). However, even doing that may not be worth the trouble. Why? Because to do Newton-Rapheson, you need to start the N-R process with a value near the root you're trying to find. So one way or another, you're going to need a reasonable estimate of isqrt(N).

So, what are other ways to get a decent estimate of sqrt(N)? Again subject to the constraint that the estimate must not in any circumstances be less than sqrt(N). Hacker's Delight (which you should read) suggests just using the next power of two greater than sqrt(n), and gives four lines of branch-less C code to compute it. However, I think we can do better...

Observation: If N contains D digits, then sqrt(N) contains D/2 digits. This gives us order of magnitude.

Then, we can do a table lookup on the first two digits of N:

00-03: 2
04-08: 3
9-15: 4
16-24: 5
25-35: 6
36-48: 7
49-63: 8
64-80: 9
81-99: 10

(If you actually implement this algorithm, I suggest you express the above table as a nine item array. 2-10 are your array indices and 3, 8, 15, 24, etc are the values in the corresponding array slot. Walk the array and compare the value in each slot with your first two digits of N. Stop when first two digits of N are greater, and then go back one index. The index value itself is your table lookup number. Why do it this way? Because we're on a space-constrained system. So a worst-case twenty instruction lookup is less bad than a hundred item array.)

Now we take the table lookup number, slap on D/2 zeros, and voila - we have our estimate. And due to the way the table is structured, it's guaranteed to be an overestimate. Exactly what we want.

Example: Estimate the square root of N = 4,294,967,197 which is a prime number near 2^32. sqrt(N) = 65535.999244689937, so our estimate must not be below 65536.

There are 10 digits in N, so there will be 5 digits in the estimate. The first two digits of N are 42, so our lookup is 7. Thus our estimate is 7 * 10e5 = 70000.

How good an estimate is that? 70000 / 65536 = 1.068115..., so our estimate is within 7%. And, as required, not less than the real square root.

If you're still sweating the difference between the estimate and the correct number, then go ahead and do a couple iterations of Newton-Rapheson with the estimate. N-R converges quadratically, so even three iterations should get you almost an order of magnitude improvement.

There are many ways to optimize the above for binary representation, but I leave that as an exercise to the reader.


(Eh? You want to know an efficient way to determine the number of digits in N? Fine, ya lazy bum, I'll google it for you: http://stackoverflow.com/questions/1489830/efficient-way-to-determine-number-of-digits-in-an-integer

What? You can't figure out an efficient way to determine the first two digits of a binary number on a CPU without hardware divide? 2^4 = 16, mang! Find the most significant 1 bit, and the next 3 after that. Those four bits determine the first two base-ten digits of the number. Finding most significant 1 bit? Binary search by masking half the bits (the least significant half) and comparing with zero.

Jeez, you ask a lot of questions!)

Oh the lulz...

One our our techs at work was tasked with repairing and testing a very large (1,000 W) power supply unit. Meet the Sorensen DCS 20-50:


The front panel

( Read more...Collapse )

Post-script: A fresh set of leads was plugged into the meter. The prongs that held the HRC fuse inside had melted off the PCB, but aside from the 20A current measurement mode, the meter appears to be working just fine! I tip my hat to you, Wavetek - that is one tough meter!

So, I learned something today. If you need a finely variable resistor with extremely low analog distortion (for say, your high-grade electronic music synthesizer) they make opto-couplers based on a light-dependent resistor (LDR). Current through an LED shines light onto the LDR, which results in a true analog variable resistor. But the cool thing is that the resistance can be easily controlled by other electronics, instead of by some knob the user has to twiddle. Useful, and a bit tricky to do well any other way. Particularly if very analog-y things like THD actually matter. A very handy building block for making true-analog (stepless) AGCs.

http://en.wikipedia.org/wiki/Resistive_opto-isolator

( PicsCollapse )

I was also surprised to see a number of PC modders walking around toting their cases. There were a number of legitimate PC parts for sale. The customers would bring their PCs and install the new parts in the shop to make sure that they worked correctly. It's not like there would be any return policy or warranty once they left.

I really don't think my photos are even coming close to capturing the absurdity and enormity of this place. Ten stories of tons of little kiosks selling all kinds of junk.

[...]

I still can't believe how incredibly cheap everything was. I would pay anything to have a market like this near my home just so I could get some parts same-day, and yet here are all the parts I could ever need for prices that I can hardly believe. We purchased four micro-switches along with two rocker and two momentary push-button switches, and the bill ran us about $2 USD. Just one of the micro-switches on Digikey would have run us almost half that. I guess a lot of the value in the parts we buy in the States must be added by shipping costs.

http://ch00ftech.com/2012/09/10/china-is-awesome/

You remember when Steve Jobs said: "Those jobs aren't coming back"? This is why.

"Boston Dynamics' Cheetah robot has just set a new record for legged robots by sprinting at 28.3 mph. This, incidentally, is also faster than Olympic (human) champion Usain Bolt, who set the world record for the 100 meter dash with a speed of 27.8 mph back in 2009. Yes, this means that now there is officially no escape from a robot cheetah on a treadmill. You've been warned."

http://spectrum.ieee.org/automaton/robotics/military-robots/boston-dynamics-cheetah-robot-now-faster-than-fastest-human?utm_source=feedburner&utm_medium=feed&utm_campaign=Feed%3A+IeeeSpectrumFullText+%28IEEE+Spectrum+Full+Text%29

Moffat Tunnel to Heart Lake is one of my favorite hikes in Colorado. It's fairly long at 8.4 miles (and 2100 ft of vertical), but I find the scenery well worth it. I didn't get pictures the first time I did this hike, about three years back. But this time...



The drive up is on (well maintained) dirt road for the last several miles, and there are multiple railroad crossings.

( Read more...Collapse )

You can dredge up my favorite roommate from college and throw him at me, but it's still not gonna prevent me from moving out of the People's Republic of Boulder.

You want to keep me here, this is what you're going to have to swing:

A decent apartment (need not be big, but not a rathole), within easy drive of Foothills (mostly rights, no difficult or long-wait lefts), south of Arapahoe (I am NOT wading across that crap every morning), less than $650/mo.

Get on it - you only have a couple of weeks.

The fact that I've been able to avoid XML until now is - I think - generally a positive reflection on my software engineering instincts. When XML was a big new thing, I took one look at it and said to myself: "Uh, yeah... no. I'll just be over here with my C and my micro-controllers and stuff. Y'all have fun with that." As it turns out I called that correctly. It's nice to get one right.

But I'm also lucky that today, in the here-and-now, we actually know that XML isn't the best way to do a lot of the things that its advocates claim(ed) it should be used for. Today we can point at JSON or CSV or whatever and say: "That works (much) better." If you were a programmer in 2003 and thought XML sucked, you didn't have anything well-known to counter it with. And so quite possibly got forced to use it.

So forgive the "old news" flavor of this rant. Everyone who was forced to use XML (which is probably nearly everybody by now) has already learned these lessons. I've just been lucky enough to not have to use XML in any serious capacity... until recently.

---

XML comments are weapons-grade fail.

First, let's face it: XML got comments wrong from the very start. The mere idea of using one string ("!--") to open a comment, and then a different string ("--") to close it, was flat out stupid to begin with. What, exactly, was wrong with <-- comment --> ? Would that have been too easy to read? Too easy to type?

But of course XML couldn't stop failing there...

You can't put the string "--" inside a comment.

<!-- This is the first line of a comment.
  -- This is the second line of a comment.
  -->

If you do something like that, get ready to see:

ERROR caused by: org.yackity.smackity.WhackIty.JackIty.HackIty.OhGodHelpMe.ICanSeeForever.YouAreInAMazeOfTwistyLittleExeption
*** String '--' not allowed in comment at [row,col {unknown-source}]: [37,6]

Stop and think for a minute about how incredibly stupid this is. The string "--" is not "<--", nor is it "-->". Thus, "--" should have no significance what so ever unless it is immediately attached to a "!" or ">" character. There is quite literally no reason at all to disallow "--" inside a comment.

Just to drive the point home, let's show an example of what would happen if we used some other string instead of "--". How about "fish"?

<!fish This is a fish. fish>

That would be invalid XML. Because the same word that came after the exclamation point, was also found again in the comment.

The level of brain death required to accept this state of affairs even temporarily, much less advocate this as a global standard to be used for decades... is just staggering.

But did XML cease its parade of comment failure there? Oh no...

You can't comment out an attribute.

Wanting to commenting out an individual attribute is a perfectly normal and reasonable thing to do. Something you'd clearly anticipate someone wanting to do, among other occasions, during process of debugging. But XML won't let you do it:

<sometag
  firstattrib="a"
<!--  secondattrib="b"  -->
  thirdattrib="c"
  fourthattrib="d">
</tag>

Or, suppose you're trying to explain why an attribute is set the way it is...

<sometag
  firstattrib="a"
  secondattrib="b"      <!-- Reticulates splines optimally. -->
  thirdattrib="c"
  fourthattrib="d">
</tag>

In both cases, your XML parser will shit all over itself at secondattrib. In XML you simply cannot have comments anywhere in a list of attributes. Period. Why? Because XML comments are made of pure fail.

!-- SPECIAL BONUS FAIL --

XML's <xs:sequence> is used all over the place in XML schema definition files. This allows the schema designer to enforce the exact order of sub-tags with a tag. Which in turn allows the XML parser to reject a perfectly valid XML document for no other reason than the order of the sub-elements inside some tag was different than it expected. E.g, this works fine:

<tag>
 <dog>lassie</dog>
 <cat>mittens</cat>
</tag>

But this blows right the hell up:

<tag>
 <cat>mittens</cat>
 <dog>lassie</dog>
</tag>

I honestly don't know why <xs:sequence> was even created. I've been thinking about this for a week and I can neither think of, nor find via googling, any example anywhere that shows a valid need to enforce the order of child tags within a tag. The whole point of having a Data Description Language is that doing so allows the computer to take care of the little bullshit things - like what order some arbitrary list of items is given in. But XML schemas far and wide enforce bullshit ordering with <xs:sequence>. Why? Because screw you, that's why!


Considering that XML requires a sophisticated Turing-complete parser to parse correctly, the fact that it can't make a single one of the above simple and obvious things work is very impressive. XML has accomplished something that's rare even in the bug-ridden and incompatible realm of software: it has managed to create the worst of all possible worlds.

So, why does this incredible heap of crap survive? Are we, the software engineers, REALLY THAT STUPID?

Yes. Yes we are.

In 2.5 years it will be 2015. And in 2015, hundreds of millions upon hundreds of millions of lines of code will still depend on - or even be written specifically to support - XML. Because we as software engineers are too damn stupid, too damn lazy, and too damn cowardly to put a bullet in this disease-ridden corpse that never should have won out over plain old SGML in the first place.

tl;dr - Screw XML. Screw it forever. XML is the herpes of the software universe.




And to my fellow software "engineers": if you advocate the use of XML in a new project that could just as easily use JSON, CSV, Windows .INI file format, or any of dozens of other far saner options... shoot yourself in the head you are a bad person and you should feel bad. (I understand, however, if you got stuck with a codebase that is already deeply XML-dependent. My condolences. Welcome to the club.)

( Large imageCollapse )

Why am I cloning JBoss? Because to understand how to get the config files right, I had to compile a debug version and single-step it.

What's what you say? I might be feeling "not impressed" with JBoss? Perhaps I'm thinking what JWZ said about the time-value of software? Well, I will neither confirm nor deny such outrageous accusations! ;]

See also http://hwellmann.blogspot.com/2011/06/java-ee-6-server-comparison-jboss.html?showComment=1310532902809#c669989613092099368 , particularly Craig Ringer's comment at the bottom.

300 years ago, Newton posed the problem of finding a closed form equation to model the motion of a projectile acting under the influence of both gravity and air friction. He couldn't solve it, and until recently nobody knew if there was an equation that did describe it.

Turns out some Indian kid who recently moved to Germany found said closed-form equation.

The problem he solved is as follows:

Let (x(t),y(t)) be the position of a particle at time t. Let g be the acceleration due to gravity and c the constant of friction. Solve the differential equation:

(x''(t)2 + (y''(t)+g)2 )1/2 = c*(x'(t)2 + y'(t)2 )

subject to the constraint that (x''(t),y''(t)+g) is always opposite in direction to (x'(t),y'(t)).

Finding the general solution to this differential equation will find the general solution for the path of a particle which has drag proportional to the square of the velocity (and opposite in direction).

http://www.reddit.com/r/worldnews/comments/u7551/teen_solves_newtons_300yearold_riddle_an/c4sxd91

Basically, given the coefficient of air friction and the force of gravity, and a particle's initial velocity vector, this allows you to calculate its velocity vector at any later time.

This should be a good thing for video games. Making objects move through the air realistically just got a whole lot easier. The immediately obvious applications are sports games - tennis, golf, baseball - which use relatively small round objects with easily defined coefficients of friction. In the long run, all game physics should get more accurate and faster as a result of this.

...or The Silent are really interested in some health insurance!

I've been spending a lot of time at work lately debugging Java. The details are not particularly important, other than to note that the popular description of JavaEE as "the new COBOL" is deadly accurate.

Most of you whipper-snappers probably use Eclipse to do your debugging these days. And that works quite well as long as you happened to compile the code you're debugging. But what happens when you didn't compile the code you're debugging? With Eclipse, you're pretty much screwed. Even if you create a fake project and link in the source, it still never really works quite right. Breakpoints often don't break. Eclipse often can't figure out which line you're actually executing. Etc.

So let's talk about going old-school - enter jdb. Never really intended to be more that a proof of concept for the JPDA, it actually turns out to be surprisingly useful when you need to debug something you don't have source code for and/or didn't compile yourself.

One nice thing about jdb is that if you have a JDK, then you have a copy of it. It's been a standard tool since Java 1.2. If you're on Windows, Unix, a Mac and have installed a JDK, then jdb(.exe) will be waiting in $JDK_HOME/bin/.

Another thing you may be surprised to hear about jdb is that it can do remote socket debug just like Eclipse can. This isn't well documented, so I'll give you the magic invocation here:

First you start the remote program you want to debug on myserver.com with something like:

java -agentlib:jdwp=transport=dt_socket,server=y,address=8787 myClass

Then on your local machine, run:

jdb -connect com.sun.jdi.SocketAttach:hostname=myserver.com,port=8787


Here's a quick cheat-sheet to get you started with the obvious stuff:

stop in com.mydomain.mypackage.myclass.mymethod         # Set breakpoint on method entry
clear   # List (no args) or clear (with args) breakpoints
use /home/mydir/sourcecodedir/     # Set source code path
list    # List source code lines
next    # steps OVER method calls
step    # steps INTO method calls
step up # run until current method returns
cont    # continue exection after breakpoint
print (somevar)   # Show current value of somevar

All pretty standard, I know. But it should be noted that all of the above work whether you have source code or not, which beats the hell out of Eclipse. Now, how about some stuff that's a little more fun?

classpath     # Print JVM's classpath
disablegc (expr)   # prevent garbage collection of an object
classes                   # list all currently loaded classes
class org.package.class   # show details of named class
methods com.this.class    # list a class's methods
fields com.that.class     # list a class's fields
eval (java expression)  # Run arbitrary java code, alter program state at will
redefine com.some.class newcode.class  # Load new .class file to redefine an existing class

Some interesting possibilities there, eh? eval is particularly fun. Need to delete an item out of a HashMap? Just eval myHashMap.remove("thiskey") and you're done. (And yes, Eclipse's debug perspective can do this too if you know how... but how many people do?)

The possibilities for redefine are especially amusing to contemplate...

This is arguably the best thing ever: http://labs.spritelink.net/living-with-windows-7

Further explanation of UserPreferencesMask: http://technet.microsoft.com/en-us/library/cc957204.aspx

Note: Bit 0x40 ("Active window tracking Z order") is basically equivalent to "autoraise" in X. Clear the bit to enable autoraise (default), set the bit to disable autoraise.

In my Windows 7 installation, "ActiveWndTrkTimeout" is set to 500 (ms) by default, which is actually a pretty good default, maybe even a tiny bit fast. See http://technet.microsoft.com/en-us/library/cc957203.aspx

Edit: After living with it for about a week, I think it could use some improvement. It needs a "if the cursor sits still for X time, auto-raise. Otherwise don't." type of deal. It's annoying to be moving across windows to the other monitor and have them all auto-raise because they're wide and you stay inside them for .5 sec as you move the cursor across.

http://www.quickmeme.com/meme/3p77cy/

http://stackoverflow.com/questions/3337056/convenient-way-to-parse-incoming-multipart-form-data-parameters-in-a-servlet

Why would we want our convenience methods that work for every other kind of HTTP transaction to work the same way for multi-part POST transactions? That's crazy talk. You must be some kinda person who believes that libraries and frameworks are supposed to make life easier for the application programmer, or something. Nutjob!

I constantly see people on Reddit /r/ece, /r/electronics, etc asking for advice on how to drive LEDs. It happens at least once a week. The classic approach is to take the input voltage, subtract the LED's forward voltage, and then use V = IR to compute the appropriate resistor. And that does work.

( But there's another way. In my opinion, a better way.Collapse )

Here it is:


Click on the image to open circuit simulation in a new window/tab. (NOTE: Requires Java capable browser.)

Simple, no? The only thing you need to know is how to calculate the resistor. Here's the formula:

Rbase = 100 * ((Vconstant - 0.65) / Iconstant)

( Read more...Collapse )

( Code...Collapse )

I created this algorithm as a result of reading a post on Reddit that showed some shockingly poor performance for intrinsic software "%" operator in some C compilers for microcontrollers which don't have hardware divide.

How does the algorithm work? Well, the mathematical definition of modulo is:

y % x = y - (x * int(y/x))

The trick this algorithm employs is to do a kind of weirdo binary search to find (x * int(y/x)), without ever directly computing int(y/x), or using division.

( Read more...Collapse )

Is it possible to do this faster? I strongly suspect so. As the Wikipedia link given below notes, it is possible to reduce (y % x) to (y & (x-1)) when x is a power of 2. Seems to me that trick should be exploitable to bring the time to compute modulo down even farther. But in any event, the above unsophisticated and unoptimized algorithm should still be a very large improvement over modulo implemented via a software divide routine... as some people's compilers are probably doing now.


See also:

http://en.wikipedia.org/wiki/Modulo_operation#Performance_issues

http://graphics.stanford.edu/~seander/bithacks.html#ModulusDivisionEasy

http://stackoverflow.com/questions/2566010/fastest-way-to-calculate-a-128-bit-integer-modulo-a-64-bit-integer

I haven't had much chance to play RAGE. Job hunt is taking almost all my time. However, I think I have found some things worth sharing...

( Trivial.Collapse )

( Update 2012/02/22Collapse )

http://cds.linear.com/docs/Application%20Note/an81f.pdf

From the excellent Reading Jim Williams blog.

After seeing this, I can't believe we're still using magnetic core transformers. I realize they're good for high-current, low-frequency applications. But this is so much better for LCD backlights, I can't believe it hasn't come to utterly dominate the marketplace.

This is probably how the people that invented fuel injection way back in the 1920's felt. "Why isn't everyone using this??" :P

But my friend decided to buy some other blu-ray discs. Or at least he tried to, until we were “assisted” by a young, poorly groomed sales clerk from the TV department, who wandered over to interrogate us. What kind of TV do you have? Do you have a cable service, or a satellite service? Do you have a triple play service plan?

He was clearly—and clumsily–trying to sell some alternative. (My guess is CinemaNow, Best Buy’s private label on-demand content service.) My friend politely but firmly told him he was not interested in switching his service from Comcast. I tried to change the subject by asking if there was a separate bin for 3D blu rays; he didn’t know.

The used car style questions continued. “I have just one last question for you,” he finally said to my friend. “How much do you pay Comcast every month?” My friend is too polite. “How is that any of your business?” I asked him. “All right then,” he said, the fake smile unaffected, “You folks have a nice day.” He slinked back to his pit.

As a sometime business school professor, I could just imagine the conversation with the TV department manager the day before. “Corporate says we have to work on what’s called up-selling and cross-selling,” the clerk was informed in lieu of actual training on either the products or effective sales. “Whenever you aren’t with a customer, you need to be roaming the floor pushing our deal with CinemaNow. At the end of the day, I want to know how many people you’ve approached.”

But this is hardly customer service. It’s actually getting in the way of a customer who’s trying to self-service because there’s no one around who can answer a basic question about the store’s confusing layout. It’s anti-service.

http://www.forbes.com/sites/larrydownes/2012/01/02/why-best-buy-is-going-out-of-business-gradually/

Beast Buy is founded on the idea of anti-service. It's their bread and butter. And they're far, far too stupid to know that they're cutting their own throats. Personally, having worked there, I don't think it could happen to a nicer company. I will throw a party when Best Buy finally dies.

So amishx64 @ Reddit said they wanted a medium voltage, high amp regulator. Specifically, something to regulate 76 volts down to 70, and do so at a current of 8 amps(!).

( To buy or to build...Collapse )

That decided, now it was mainly just a question of using the classic negative-feedback regulator architecture and adapting it to P-channel MOSFETs. I'm pretty pleased with the resulting circuit:



Falstad Circuit Sim code: http://www.gully.org/~mackys/circuits/linreg-opamp.txt

( Read more...Collapse )

Notice that Perl requires over sixty seconds to match a 29-character string. The other approach, labeled Thompson NFA for reasons that will be explained later, requires twenty microseconds to match the string. That's not a typo. The Perl graph plots time in seconds, while the Thompson NFA graph plots time in microseconds: the Thompson NFA implementation is a million times faster than Perl when running on a miniscule 29-character string. The trends shown in the graph continue: the Thompson NFA handles a 100-character string in under 200 microseconds, while Perl would require over 1015 years. (Perl is only the most conspicuous example of a large number of popular programs that use the same algorithm; the above graph could have been Python, or PHP, or Ruby, or many other languages. A more detailed graph later in this article presents data for other implementations.)

It may be hard to believe the graphs: perhaps you've used Perl, and it never seemed like regular expression matching was particularly slow. Most of the time, in fact, regular expression matching in Perl is fast enough. As the graph shows, though, it is possible to write so-called "pathological" regular expressions that Perl matches very very slowly. In contrast, there are no regular expressions that are pathological for the Thompson NFA implementation. Seeing the two graphs side by side prompts the question, "why doesn't Perl use the Thompson NFA approach?" It can, it should, and that's what the rest of this article is about.

http://swtch.com/~rsc/regexp/regexp1.html

These aren't used much because the implementation is a little more difficult, and you have to give up some things, like backtracking. Still, if your program is limited by regex matching speed (most aren't, but just in case) you should consider using an NFA regex package, instead of the default DFA regexes that come with most languages/libraries.

If you enjoy TEH DEVIL MUSIC, this may be relevant to your interests:

http://www.facebook.com/media/set/?set=a.272692642768878.63482.100000844344684&type=1&l=560f04be86

Ever wondered if you can synchronize your Windows (2000 or later) computer's clock with an NTP server? Yes, you can download NTP synchronizer program if you want. But I am lazy and hate waiting for downloads, so I wanted to do this with just stuff that ships with Win7.

Turns out you can synchronize with time.windows.com, which is accurate to approximately 1.5 seconds. If that's good enough for you, here's a way to do it without downloading anything:

First, click on the Start menu at lower-left. Type in "cmd". Windows will show you a "cmd.exe" program. Right-click on it and then click "Run as administrator". Now a special "administrator" command prompt will come up. Type in:

net start w32time

w32tm /config /update /manualpeerlist:time.windows.com

w32tm /resync

net stop w32time

The "net start" command starts a windows service that synchronizes clocks, the "w32tm /config" commands tells it you want to synchronize with time.microsoft.com, the "w32tm /resync" command says "okay, actually do a sync now", and finally the "net stop" command shuts down the sync service, since the clock has successfully been sync'd.

It's a lot more convoluted and annoying than Linux's "ntpdate", but I guess that's Windows for you. :P If you anticipate doing this frequently, by all means cut and paste the above into a batch file named "synctime.bat" or whatever. Just remember that you need to run it as administrator, or it won't work.


Google-bait: NTP server manual time synchronization windows

http://www.androidzoom.com/android_applications/productivity/droid48_wex.html

Aww yee, muffins...

No doubt I've been working too much. This weekend was the most fun I've had in two months at least. Let's name and praise!

Saturday Chuck invited me to come see an Impulse Theater show. This is the improv group that performs in the basement of the Wynkoop Brewery. Afterward we dropped by Watercourse Foods (near 17 & Emerson) for some of the best vegan food I've ever had.

Sunday during the day I got to help Simon move. ("Friends help you move - real friends help you move bodies.") There's no shortage of interesting people around Simon, and it was cool to meet everyone. I was actually disappointed how many people showed up - I didn't even get to do any heavy lifting. After how hard I worked Simon during my move, I was ready to move mountains for him.

Sunday evening I hooked up with j_b, Morgan and Shawn. Bailey and I got dinner at a little Chinese place down at Alameda and Logan in Wash Park. It is evidently under new management and the food has taken a major turn for the better. I was literally licking my plate (for real, ask Bailey) after I was done with my shrimp & vegetables. The food is excellent, and it isn't expensive either. You may have noticed I haven't named the place - that's because I'm not sure I remember the name right, and I don't want to give you the old name, as the food didn't used to be as good. (I'll try and find out what the name of the place was, and toss an edit in here.)


http://www.imdb.com/title/tt1270262/

After dinner we went and saw The Devil's Double at The Mayan. This is a movie about the life of Uday Hussein, Saddam Hussein's son. This is an amazing movie, and it's a damnable shame that it will never be shown in mainstream theaters. The reason is simple: it's completely unflinching and it pulls no punches. Torture, rape and endless drug use were Uday's weekly routine, and the movie shows all of it in graphic detail. Dominic Cooper turns in an incredible performance as both Uday AND his body double Latif Yahia. Top it off with a budget of $24 million and direction by Lee Tamahori (Die Another Day, Along Came A Spider), and you have what really should be the movie of the summer - if anyone even knew it existed. GO SEE THIS. You're missing out on what may be the best movie of the year if you don't.

Video games are art, and they deserve the exact same First Amendment protections as books, comics, plays and all the rest, the U.S. Supreme Court said Monday in a ruling about the sale of violent video games in California.

California had tried to argue that video games are inherently different from these other mediums because they are "interactive." So if a kid has to pick up a controller and hit the B button - over and over again until he starts to get thumb arthritis - to kill a person in a video game, that's different from reading about a similar murder, the state said.

The high court didn't buy that argument, however.

[...]

"Like the protected books, plays, and movies that preceded them, video games communicate ideas - and even social messages - through many familiar literary devices (such as characters, dialogue, plot, and music) and through features distinctive to the medium (such as the player's interaction with the virtual world). That suffices to confer First Amendment protection."

http://www.cnn.com/2011/TECH/gaming.gadgets/06/27/supreme.court.video.game.art/

And so another miserable old scold loses any claim to be able to tell those kids that they can't play on their own lawns. Excellent.

P.S. IN UR FACE, Roger Ebert! ;]

Just wanted to give a quick shout out here: I can't login to my LinkedIn profile. Consequently can't accept any invitations to link. Sorry to those who have sent them, you know who you are. I'll keep trying. (They won't even send me an email with my reset password... I swear Linkedin gets dumber every hour.)

I'm quitting PlentyOfFish.com out of sheer boredom. The last two months with an account there have completely validated my prejudice that there are no single women over 25 in Boulder. (Actually, there was one, but she evidently deleted/hid her account, so...) I suppose my timing could have been better. I created my account just before 4th of July weekend, so the two replies I did get were: "let's talk again after the 4th holidays are over." And then no messages after that. Guess I'm not very memorable. ;]

In other news of the nerdy, the wifi I'm leeching off is one whose encryption is disabled and has no password... but also has its SSID broadcast turned off. Someone thought security through obscurity actually worked! So I ask you, my fellow techies... how many gigs of sheep porn¹ per hour should I download through this person's unsecured wifi? ;]

-----
¹ Hot, hot, SEXY sheep pr0n...

By contrast, EVE takes a much smaller player base - perhaps 450,000 - but jams all these monkeys into one barrel, a barrel from which there is no escape - no 'other server' to flee to and begin anew. The learning curve in EVE might as well be vertical, despite all the efforts to make the game more newbie-friendly over the years; any sort of mistake usually results in you dying horribly and losing substantial assets, which are very limited when first playing the game. Additionally, more than any other MMO, EVE relies heavily on mathematics and spreadsheets in the player-run logistics and production aspects of the game. Given the violence, loss, and (horror of horrors) math, it is only a certain sort of of monkey who not only ascends the nightmarish and Darwinian learning curve, but finds the process entertaining enough to stick around and play for more than a week. So this is EVE, a galaxy filled with socially inept spreadsheet nerds on the one hand and obsessive, ambitious griefers on the other. Resources are limited and must be fought over, and the only way out is to quit entirely.


http://www.tentonhammer.com/node/65475

I like to say, "Life is not a zero-sum game."

EVE Online... is!

Who's white, has two thumbs, and wishes he was as smart as Neil deGrasse Tyson?

(points thumbs at self) THIS GUY! ;D

I don't think C gets enough credit. Sure, C doesn't love you. C isn't about love - C is about thrills. C hangs around in the bad part of town. C knows all the gang signs. C has a motorcycle, and wears the leathers everywhere, and never wears a helmet, because that would mess up C's punked-out hair. C likes to give cops the finger and grin and speed away. Mention that you'd like something, and C will pretend to ignore you; the next day, C will bring you one, no questions asked, and toss it to you with a you-know-you-want-me smirk that makes your heart race. Where did C get it? "It fell off a truck," C says, putting away the bolt-cutters. You start to feel like C doesn't know the meaning of "private" or "protected": what C wants, C takes. This excites you. C knows how to get you anything but safety. C will give you anything but commitment

In the end, you'll leave C, not because you want something better, but because you can't handle the intensity. C says "I'm gonna live fast, die young, and leave a good-looking corpse," but you know that C can never die, not so long as C is still the fastest thing on the road.

http://dis.4chan.org/read/prog/1312655446/4

Yes, from a 4chan board. Really.

Why do I personally like C? Partly it's Baby Duck Syndrome - C was my first real language (Apple Basic doesn't count). Partly it's that I've always been a low-level guy, who likes assembler and enjoys knowing how things work behind the curtain. Being essentially a portable assembler with a veneer of high-level language applied, C appeals to me in the same way sportbikes do. You're close to the metal, but not so close you're getting burned. You're just close enough to the machine to enjoy it, but the rough edges have been mostly rounded to where it's mostly comfortable. High power, but reasonable comfort.

My mom talked me into voting for Obama the first time. Not again. Fool me once, shame on you. Fool me twice, shame on me.

If Ron Paul runs, I'll vote for him knowing full well he won't win. If he doesn't, I may not bother to vote at all, or I might write in Anton LeVay. (It's time to stop voting for the lesser evil. :P)

What he found is that the batteries are shipped from the factory in a state called "sealed mode" and that there's a four-byte password that's required to change that. By analyzing a couple of updates that Apple had sent to fix problems in the batteries in the past, Miller found that password and was able to put the battery into "unsealed mode."

From there, he could make a few small changes to the firmware, but not what he really wanted. So he poked around a bit more and found that a second password was required to move the battery into full access mode, which gave him the ability to make any changes he wished. That password is a default set at the factory and it's not changed on laptops before they're shipped. Once he had that, Miller found he could do a lot of interesting things with the battery.

"That lets you access it at the same level as the factory can," he said. "You can read all the firmware, make changes to the code, do whatever you want. And those code changes will survive a reinstall of the OS, so you could imagine writing malware that could hide on the chip on the battery. You'd need a vulnerability in the OS or something that the battery could then attack, though."

http://www.schneier.com/blog/archives/2011/07/hacking_apple_l.html

Making your batteries a different size and/or shape than others? Probably had a good reason for it.

Making a customized connector for your batteries? That's starting to get a little silly, but maybe it was to lower cost, or enable the flow of more watts between battery and computer.

Adding extra expense and extra complexity to both the battery and the driver software by putting not one but two layers of password lockout... on a damn battery??

That's not evil, monopolistic or specifically designed to avoid interoperability and guarantee your ability to price-gouge your customers, Apple. Nope. Not at all. Stay classy, you guys. And by all means, continue this kind of behavior. You're doing a stellar job of niche-marketing yourself right into oblivion.

The fact that such added complexity provides a potential opening for BIOS viruses that can't be detected by normal means and will survive an OS reinstall? That's just the icing on the cake. Memo to geniuses: Haven't you guys ever heard of a fuse? If you don't want customers (or viruses) casually messing with your battery's firmware, then you should have put a twenty cent chip fuse on your $100 battery, and blow it as the last step of the factory QC process. Then nobody can change your device's factory settings without at least having to take it apart.

(Yeah, I know: "So sorry - we can't hear you over the sound of our thousand-foot high piles of cash!" -Apple. Yeah, well, you guys be sure to let me know when you find your thousand-foot high pile of brains! What's that? You say you don't have one of those? Well then...)

http://www.damninteresting.com/the-wrath-of-the-killdozer/

Some thin-skinned person might say: "How you can laugh at such a horrible tragedy??" I ask: "What tragedy?" Heemeyer didn't manage to kill or even seriously injure anyone. Not a single person. He did property damage only, and then he paid with his life. That's why this is worthy fodder for humor - because nobody else was hurt. The fact that Heemeyer was clearly bonkers, and that he built an unstoppable redneck tank, only make it all the more bizarre and thus more amusing.