l i n u x - u s e r s - g r o u p - o f - d a v i s
Next Meeting:
July 7: Social gathering
Next Installfest:
Latest News:
Jun. 14: June LUGOD meeting cancelled
Page last updated:
2002 Aug 08 14:00

The following is an archive of a post made to our 'vox mailing list' by one of its subscribers.

Report this post as spam:

(Enter your email address)
[vox] Re: [vox-tech] shell script challenge - Now MD5sum erratia
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[vox] Re: [vox-tech] shell script challenge - Now MD5sum erratia

begin Micah Cowan <micah@cowan.name> 
> Samuel Merritt writes:
>  > 
>  > Micah Cowan writes: 
>  > > [snip]
>  > > But it's a heluva lot better than running diff from one file to every
>  > > other file - a factorial-time operation! :)
>  > 
>  > I think it's only quadratic-time. If you have N files, you need to diff
>  > every possible pair of files to make sure that all the files are unique.
>  > So,  you pick a file F, and compare it with all the other N-1 files. Since
>  > you have to do this for all N files, and diff(file1, file2) is the same as
>  > diff(file2, file1), that's only N(N-1)/2 diffs that have to be done. 
>  > 
>  > This is exactly like a question you see in math puzzle books sometimes: If
>  > there's a group of N people and each person shakes hands with every other
>  > person, how many handshakes are there? 
> Sorry: I was thinking of sums and not multiplication (which is what
> factorial is). I meant: N + N-1 + N-2 + ... + N-(N-1), which is
> equivalent to N(N+1)/2.
(redirected to vox since i'm not adding anything to the conversation)

this is totally irrelvent to the discussion, but very cute.  the proof
of that is to do the sum twice:

  N  +  N-1  +   N-2   +   N-3  +  ...  +  3   +    2   +  1    <- sum1
  1  +   2   +    3    +    4   +  ...  + N-2  +   N-1  +  N    <- sum2
 N+1 +  N+1  +   N+1   +   N+1  +  ...  + N+1  +  N+1   +  N+1  <- 2*sum

so we have (N+1) taken N times.  therefore, both sums taken together is
N*(N+1).  since we did the sum twice, we need to divide by 2.

1 + 2 + ... + N-1 + N  =  N(N+1)/2

this was attributed to the german mathematician gauss.  the story says
that when he was 8 years old, he mouthed off to a teacher.  as
punishment, the teacher said he had to add all the numbers from 1
through 100.   he developed this to get the job done quickly.


GPG Fingerprint: B9F1 6CF3 47C4 7CD8 D33E  70A9 A3B9 1945 67EA 951D
vox mailing list

LUGOD Group on LinkedIn
Sign up for LUGOD event announcements
Your email address:
LUGOD Group on Facebook
'Like' LUGOD on Facebook:

Hosting provided by:
Sunset Systems
Sunset Systems offers preconfigured Linux systems, remote system administration and custom software development.

LUGOD: Linux Users' Group of Davis
PO Box 2082, Davis, CA 95617
Contact Us

LUGOD is a 501(c)7 non-profit organization
based in Davis, California
and serving the Sacramento area.
"Linux" is a trademark of Linus Torvalds.

Sponsored in part by:
Appahost Applications
For a significant contribution towards our projector, and a generous donation to allow us to continue meeting at the Davis Library.