maybe not exactly what you were expecting Detro, but still…

My dad is possibly the person least unable to use any piece of technology other than a car stereo from the 80s.

Mmm, this means your dad is very good with technology.

I hated phones, smart-phones, and every other mobile device on the planet in the pre-iPhone era. Completely. I couldn’t use any of them. Then, iPhone came. And in the post-iPhone era iPhone is still the only mobile device I can use.

I tried Nexus One three times, in three different situation. And each time I got absurdly upset in less than 30 secs. It does not matter how technically cool, full featured, and bleeding edge it can be. If I can’t use it, it’s rubbish.

One more proof about iPhone being the only usable device on Earth, is my father. My dad is possibly the person least unable to use any piece of technology other than a car stereo from the 80s. A few days ago I let him try to use the iPhone: he managed to call, take a photo, and record a video without making the universe collapse. Incredible achievement.

I would say the most annoying is that when incoming call comes in or sms(calendar) you have to close your application, i would think if Apple would sort this out it will give people much more sense of multi tasking.

They should “copy” Android on this. Problem is that iPhone (un)fortunately is not based on a runtime. But this could be worked around using some “message registration and delivery” UDEV-like.

Plus, i think Push eats up battery in less then 24 hours, which indicates their networking stack is probably not as good as say Nokia, but if they can improve that that is a good way to stay connected. I would also believe some application should be given ability to run in background, for example Pandora or Spotify, but most of the apps or games don’t need to be in background.

Agreed 100%: Nokia still has the best Network/Telephony stack hands down. And I believe Apple is going to do something to make “background apps” possible.

The latter will happen, again, when they manage to define an “interaction flow” where the User can understand what’s going on. And they have the ability to do it. Hands down .

I would say the most annoying is that when incoming call comes in or sms(calendar) you have to close your application, i would think if Apple would sort this out it will give people much more sense of multi tasking. Plus, i think Push eats up battery in less then 24 hours, which indicates their networking stack is probably not as good as say Nokia, but if they can improve that that is a good way to stay connected. I would also believe some application should be given ability to run in background, for example Pandora or Spotify, but most of the apps or games don’t need to be in background.

Apple already improved review process, now it is much faster (a friends free app took only 2 days to appear in appstore), the other things they could improve is have a checklist and some tools they run to be able to run as a developer.

So, iPhone still rulez, and what is so most cool about it as industry has managed to catchup to Apple which is good for average joe, but Apple will be moving forward in a few month setting new finishing lines.

Some IM clients have Link-Local XMPP already: iChat should support it, pidgin (and maybe other libpurple based clients) does, the teleapthy framework used by the GNOME DE also has good support for it. You can even get it to work on MS Windows.

I am collecting some links for the blog post to come. I’ll ping you here when it’s up.

Not sure. I’ll try to compile Avahi, that seems to be the most “known and stable” opensource implementation of Zeroconf, and take it from there.

Thanks a lot.

no broadcasting needed for actual communication, just relying on multicast DNS for nodes discovery (Zeroconf, or Bonjour in apple-land) is enough, check out Link-Local XMPP: http://xmpp.org/extensions/xep-0174.html

Since it’s XMPP I guess you can use all the cool stuff on top of it, audio and video calls via jingle, end-to-end encryption, and whatnot; I haven’t tried such advanced uses tho, I just use it to chat on the lan.

There are already IM clients supporting this; it’s curios I’ve been thinking about blogging just about that lately, maybe I should really do it. Let me know if you need more details.

Take care,
Antonio

What I should have said is that:

the complexity is an Ω(n * log(n)) and O(n2).

Anyway, resetting the problem by B = A is also wrong, in my pseudo-code, because A never changes.

Without testing it, I believe A should be updated as well every time a B “is confirmed”, which means that this bit

if (2 * D[i] > D[i + 1]) then
// reset the problem
B = A;
S[i+1] = 0
endif

should become

if (2 * D[i] > D[i + 1]) then
// reset the problem
B = A
S[i+1] = 0
else
A = B
endif

Let’s try again from “Given the condition above,

2*D[n-2] ≤ 2*D[n-1]

is true, implying

2*D[n-1] ≤ D[n] => 2*D[n-2] ≤ 2*D[n-1] ≤ D[n]

By induction you can verify that valid for every i and j.

D[1] < D[2] < … < D[n-2] < D[n-1] < D[n]

Given the condition above,

2*D[n-2] 2*D[n-2] ≤ 2*D[n-1] ≤ D[n]

By induction you can verify that valid for every i and j.

One small thing about your algorithm: you check “my” codition only for pairs (i,j), where j = i+1. The condition was for any pair (i,j), where j > i.

But this doesn’t change the fact that I was wrong

Thanks for commenting: I’m going to correct the post right now.

D = {1, 2, 5, 16, 30, 50}
A = 35

which verifies that condition, you can easily check that the Greedy algorithm still works.

On the other hand, you can easily embed your condition in the Greedy algorithm (see pseudo-code at the bottom of the comment), and make it works in some situations where that condition is verified, as in

D = {1, 2, 5, 10, 30, 50}
A = 63

Again, being the condition non sufficient, embedding it in the Greedy algorithm is also not sufficient and your DP solution still is the only one being correct (as in “it works in every case”).

But we can probably find a complementary condition which together with the other one will form a set of condition necessary and sufficient, and therefore the Greedy algorithm can be tweaked accordingly. Not sure, though, that this new potential condition, once implemented, will keep the computational complexity unchanged, as the other one did.

— Pseudo Code embedding the condition in Greedy algorithm:

change_coins_greedy(D[], A):
init S[n]
i = n-1
// Pick as much largest coins as possible
B = A
while ( B > 0 ) do:
// not the first coin being considered and
// the previous coin has been picked at least once
if (i 0) then
// condition to check the monetary system
if (2 * D[i] > D[i + 1]) then
// reset the problem
B = A;
S[i+1] = 0
endif
endif
S[i] = B / D[i]
B = B – S[i] * D[i]
i = i – 1
endwhile

// Set to ‘0′ the result for all the other coins
while ( i >= 0 ) do:
S[i] = 0
i = i – 1
endwhile

And in the last 2/3 months happened at least once that in, an update, the msysgit guys screwed the configuration. So, it’s not always something we can workaround.

Anyway, no prob

You are right: Branch and Condition are not the same thing. But I’m NOT assembly-oriented enough to remember to do the difference up-front.

Your post definitely saved my day! Many Thanks.

Just for completeness an UNCONDITIONAL JUMP, is also called UNCONDITIONAL BRANCH sometimes. For some, branch and condition are not the same thing. Abuse of language? Maybe, but it was functional to my joke, if nothing else (oh, it’s raining puns…).

All the best, Antonio.

But very nice indeed.

a+=b;
b=a-b;
a-=b;

Or just for fun:
a*=b;
b=a/b;
a/=b;

But of course, you would never use * and / this way

This means that no CONDITION is verified, and the Pipeline can keep prefetching.

I forgot to say that this was the MAIN reason for avoiding branching

Well, sorry for such a bad joke, the compiler is going to optimize that function out, and this was not even the point anyways

I just wanted to say: go on with these posts, some memory refreshing is always good.

I’ve run into code like this in linux once, you find another explanation on Hamming weight page on Wikipedia.

Bit-hacks are often damping indeed I felt so stupid when reading Bit Twiddling Hacks … but then I realized that maybe, in this context, “stupid” just translates to “sane”…

Ciao

• 0×1 as “never appeared”
• 0×2 as “appeared once”
• 0×4 (or, in general, > 0×2) as “appeared multiple times”

About the second point, I guess you are right: it is something dependent on the platform: if there is a specific set of registry already able to do 1-clock-heartbit AND and none for “EQUALITY COMPARISON”, then my point stands. Otherwise it’s irrelevant.
I’m unable to find a reference, but I was told looooong time ago that this was the case for ARM architectures. But, again, I could be wrong.

Any Architecture expert out there?

BUT, there is still a reason for NOT using the EQUALITY COMPARISON: given the fact that the algorithm is all designed around the concept of “bit manipulation”, it is more clear, in my opinion, to maintain constant the usage of bitwise operators. Avoids, for who reads the algorithm, to move from the mental scope of “bitwise operations” to “interger’s math”.

Thank you very much for this comments anyway, really really useful to compare with someone else that knows these matters

Your second point is interesting, can you give any references? Probably specific to platform/compiler.

About your second suggestion, I think you should check this out: http://www.cplusplus.com/reference/clibrary/cstring/memset/. The second parameter represent the initialization value: doing like you say would mean “marking all chars as present once”.

And, for your last suggestion, a “bitwise AND” is faster then using comparison. That’s why it should be used whenever possible.

Thanks.