Click here to Skip to main content
14,265,748 members

Welcome to the Lounge

   

For discussing anything related to a software developer's life. Technical discussions are encouraged, but click here to ask your programming questions.

The Lounge is rated PG. If you're about to post something you wouldn't want your kid sister to read then don't post it. No flame wars, no abusive conduct, no programming questions and please don't post ads.
 
GeneralRe: So we were hanging out Chris Meech and I, yesterday.. Pin
Pete O'Hanlon4-Aug-12 10:29
protectorPete O'Hanlon4-Aug-12 10:29 
JokeRe: So we were hanging out Chris Meech and I, yesterday.. Pin
PIEBALDconsult4-Aug-12 12:35
protectorPIEBALDconsult4-Aug-12 12:35 
GeneralRe: So we were hanging out Chris Meech and I, yesterday.. Pin
Mustafa Ismail Mustafa4-Aug-12 13:19
memberMustafa Ismail Mustafa4-Aug-12 13:19 
GeneralRe: So we were hanging out Chris Meech and I, yesterday.. Pin
Mustafa Ismail Mustafa4-Aug-12 13:16
memberMustafa Ismail Mustafa4-Aug-12 13:16 
GeneralRe: So we were hanging out Chris Meech and I, yesterday.. Pin
leppie5-Aug-12 5:47
memberleppie5-Aug-12 5:47 
GeneralRe: So we were hanging out Chris Meech and I, yesterday.. Pin
Mustafa Ismail Mustafa10-Aug-12 10:00
memberMustafa Ismail Mustafa10-Aug-12 10:00 
GeneralRe: So we were hanging out Chris Meech and I, yesterday.. Pin
leppie12-Aug-12 7:32
memberleppie12-Aug-12 7:32 
GeneralDigital roots and divisibility Pin
harold aptroot4-Aug-12 3:50
memberharold aptroot4-Aug-12 3:50 
It is well known that a number is divisible by 9 if and only if its digital root is 9.
Less well known is that a similar trick kind applies to numbers other than 9, but doesn't really work out.

In order to make this trick "work" (I'll get to why it sometimes doesn't) for number k, the digit at position i has to be multiplied by base^i - [the biggest multiple of k <= base^i] before adding it to the (modified) digital sum.

For example for k = 7, base = 10, you'd multiply the ones position by 3, the tens position by 2, the hundreds position by 6, and so forth (3, 2, 6, 4, 5, 8, then it repeats).

It does transform every multiple of 7 into a multiple of 7 (and every non-multiple-of-7 into a non-multiple-of-7), but it can be the same number, for example 14: 3 * 4 + 2 * 1 = 14, or it can even be a bigger number, for example 9.

But we're programmers, so the base isn't 10. It can be 16. 6 * 6 = 36, so every (positive integer) power of 16 ends in a 6, which means that the nearest lower multiple of 5 is only 1 away. So for k = 5, it works out to a factor of 1 at every position.

Even better, 16^n-1 is divisible by 15*, so for base 16, k = 15 works out well too, with a factor of 1 at every position. This leads to the following algorithm:
static bool IsMultipleOf15(int x)
{
    const ulong lookuptable = 0x1000200040008001; // lookup table to speed up last step
    int t = (x & 0x0F0F0F0F) + ((x & unchecked((int)0xF0F0F0F0)) >> 4);
    t = (t & 0x001F001F) + ((t & 0x1F001F00) >> 8);
    t = (t & 0x0000003F) + ((t & 0x003F0000) >> 16);
    t = (t & 0xF) + ((t & 0x70) >> 4);
    return ((lookuptable >> t) & 1) != 0;
}

15, of course, has factors 3 and 5, so the same code works to test for divisibility by 3 or 5 just by changing the lookup table to 0x9249249249249249 or 0x1084210842108421, respectively (the two of those ANDed together gives the lookup table for 15, of course). I haven't encountered a situation where this is useful; modulo by a constant is optimized by every sane compiler so this is never an optimization, just a curiosity (or perhaps something to torture interviewees with).

* I'm not really sure why - anyone? it looks like a weird mutant of x*x=1+(x-1)(x+1) to me, but as far as I can tell, it's not exactly that.
GeneralRe: Digital roots and divisibility Pin
leppie4-Aug-12 9:25
memberleppie4-Aug-12 9:25 
GeneralRe: Digital roots and divisibility Pin
harold aptroot4-Aug-12 9:34
memberharold aptroot4-Aug-12 9:34 
GeneralRe: Digital roots and divisibility Pin
harold aptroot5-Aug-12 1:23
memberharold aptroot5-Aug-12 1:23 
GeneralRe: Digital roots and divisibility Pin
Kenneth Haugland5-Aug-12 7:12
professionalKenneth Haugland5-Aug-12 7:12 
GeneralRe: Digital roots and divisibility Pin
harold aptroot5-Aug-12 8:50
memberharold aptroot5-Aug-12 8:50 
GeneralRe: Digital roots and divisibility Pin
Bassam Abdul-Baki6-Aug-12 2:47
professionalBassam Abdul-Baki6-Aug-12 2:47 
GeneralRe: Digital roots and divisibility Pin
harold aptroot6-Aug-12 3:36
memberharold aptroot6-Aug-12 3:36 
GeneralRe: Digital roots and divisibility Pin
Bassam Abdul-Baki6-Aug-12 4:06
professionalBassam Abdul-Baki6-Aug-12 4:06 
GeneralRe: Digital roots and divisibility Pin
harold aptroot6-Aug-12 4:41
memberharold aptroot6-Aug-12 4:41 
GeneralRe: Digital roots and divisibility Pin
Bassam Abdul-Baki6-Aug-12 4:45
professionalBassam Abdul-Baki6-Aug-12 4:45 
General[Solved]Is it just me or... Pin
lw@zi 4-Aug-12 2:35
professional lw@zi 4-Aug-12 2:35 
JokeRe: Is it just me or... Pin
Joan M4-Aug-12 3:29
professionalJoan M4-Aug-12 3:29 
GeneralRe: Is it just me or... Pin
OriginalGriff4-Aug-12 3:30
protectorOriginalGriff4-Aug-12 3:30 
GeneralRe: Is it just me or... Pin
DaveAuld4-Aug-12 4:57
protectorDaveAuld4-Aug-12 4:57 
GeneralRe: [Solved]Is it just me or... Pin
peterchen6-Aug-12 5:37
memberpeterchen6-Aug-12 5:37 
GeneralOscar Pistorius. PinPopular
Septimus Hedgehog4-Aug-12 0:13
memberSeptimus Hedgehog4-Aug-12 0:13 
GeneralRe: Oscar Pistorius. Pin
OriginalGriff4-Aug-12 0:28
protectorOriginalGriff4-Aug-12 0:28 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.