(sqrt (factorial 100))
Edward Huang
I tried (sqrt (factorial 100)) when I wrote a function to determine if
100! is prime. I wrote a function 'factorial' to calculate 100! and
anothor, 'prime', to check if a number x is prime. Originally I have a
list in the function 'prime':
(setq max (sqrt (factorial 100)))
because 'max' means the maximum times it should be checked from 2 to
sqrt(x), but I was warned of the message:
'*** - floating point overflow.'
How to avoid the overflow problem? My interpreter is CLISP v2.31.
Jeff Greif
sqrt (both produce answers in CormanLisp 2.5). It is more likely to use
some large-integer based algorithm, while sqrt might work only for IEEE
floats. Also, sqrt is likely to return a float, thus losing enough
precision that you will not be able to accurately bound the variable max as
you are attempting to do. If isqrt fails in CLisp, you might have to code
up an algorithm for large-integer sqrts. I can give you some help if this
is necessary.
Jeff
"Edward Huang" <s902...@ms5.pccu.edu.tw> wrote in message
news:19297054.03112...@posting.google.com...
Nils Goesche
> I tried (sqrt (factorial 100)) when I wrote a function to determine
> if 100! is prime. I wrote a function 'factorial' to calculate 100!
> and anothor, 'prime', to check if a number x is prime.
You mean, you really believe you need a computer to find out whether
100! is prime?
Regards,
--
Nils Gösche
"Don't ask for whom the <CTRL-G> tolls."
PGP key ID #xD26EF2A0
lin8080
Edward Huang schrieb:
> ... and
> anothor, 'prime', to check if a number x is prime. Originally I have a
> list in the function 'prime':
Hallo
When you look for primes, then look at this:
d s
1 1 (start)
2 2
3 3 (extra, the only one)
4 4
5 5 (could be prime)
6 6
7 11 (could be prime)
8 12 (never is prime)
9 13 (never is prime)
10 14 (never is prime)
11 15 (could be prime)
12 16 (never is prime)
13 21 (could be prime)
14 22 (never)
15 23 (never)
16 24 (never)
17 25 (could be prime)
18 26 (never)
19 31 (could be prime)
20 32 ()
21 33 ()
22 34 ()
23 35 (could be prime)
24 36 ()
25 41 (could be prime)
26 42
27 43
28 44
29 45 (could be prime)
30 46
31 51 (could be prime)
32 52
33 53
34 54
35 55 (could be prime)
36 56
37 61 (could be prime)
38 62
39 63
40 64
41 65 (could be prime)
42 66
43 111 ()
44 112
.. ...
It seems so simple when using the old way of writing numbers.
stefan
William D Clinger
> You mean, you really believe you need a computer to find out whether
> 100! is prime?
Hey, 2! is a prime. Why shouldn't there be others?
Will
Adam Warner
This is an issue of implicit integer to single-float conversion. Here's
the issue explicitly:
(sqrt (coerce (factorial 100) 'single-float)) => floating point overflow
Here is it resolved:
(sqrt (coerce (factorial 100) 'double-float)) => 9.66054943799493E78
The standard does not mandate that SQRT has to return an integer
under any circumstances ("If number is a positive rational, it is
implementation-dependent whether root is a rational or a float.")
Regards,
Adam
Adam Warner
Evaluate MOST-POSITIVE-SINGLE-FLOAT:
most-positive-single-float => 3.4028235f38
Artie Gold
"I read the news[group] today, oh boy..." ;-)
--ag
--
Artie Gold -- Austin, Texas
Oh, for the good old days of regular old SPAM.
Jason Sewall
100! + 1, that's a different story.
There isn't a machine in the world that can take 156-digit number like 100!:
9332621544394415268169923885626670049071596826438162146859296389521759999
3229915608941463976156518286253697920827223758251185210916864000000000000
000000000000
And stuff it into a regular old IEEE floating point register. You're
looking a some hard-core software-based (bignum) crunching.
Kaz Kylheku
I've never been able to overcome my amazement that 10!, 11! ... are
all divisible by 10. The list of zero digits grows, too as you get
past 100!, 1000! and so on. It's just friggin' amazing how these
factorials are such damn round numbers in the decimal system. That
kind of goes to show ya that there is, like, more to this base ten
thing than just the number of fingers on the human hand!
Espen Vestre
> That kind of goes to show ya that there is, like, more to this base ten
> thing than just the number of fingers on the human hand!
yes! stuff aura photography, the next big thing is Finding Your
Personal Faculty Number!
--
(espen)
Joe Marshall
Even weirder, it still works even if you don't count with your thumbs.
larry
prime.
The answer is no. If you want to test your prime check algorithm on
some
big numbers try finding the 41st meresenne primes.Mersenne primes are
prime numbersof the form (2^n)-1. The 39th meresenne prime occurs when
n=13,466,917 ie. (2^13,466,917 )-1 is prime. The 40th meresenne prime
has just been found(Nov 17) but they are checking the accuracy
of the computation.
Given your question, your prime checking function is probably pretty
naive
and slow.Check out primality testing algorithms on the web.
s902...@ms5.pccu.edu.tw (Edward Huang) wrote in message news:<19297054.03112...@posting.google.com>...
William D Clinger
> There isn't a machine in the world that can take 156-digit number like 100!:
>
> 9332621544394415268169923885626670049071596826438162146859296389521759999
> 3229915608941463976156518286253697920827223758251185210916864000000000000
> 000000000000
>
> And stuff it into a regular old IEEE floating point register. You're
> looking a some hard-core software-based (bignum) crunching.
It works on my machine:
> (define x (factorial 100))
x
> x
9332621544394415268169923885626670049071596826438162146859296389521759999
3229915608941463976156518286253697920827223758251185210916864000000000000
000000000000
> (exact->inexact x)
9.332621544394415e157
As the author of the library code for exact->inexact, and as the
author of the compiler that compiles it into machine code, I can
assure you that a suitable representation of x got stuffed into
a regular old IEEE floating point register. But I'll agree that
it took some hard-core number crunching to squeeze x into that
little bitty (64-bit) register.
;)
Will
Pascal Bourguignon
But all factorials are figgin' amazingly damn round numbers in ALL bases!
--
__Pascal_Bourguignon__ http://www.informatimago.com/
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Living free in Alaska or in Siberia, a grizzli's life expectancy is 35 years,
but no more than 8 years in captivity. http://www.theadvocates.org/
Pascal Bourguignon
> k...@ashi.footprints.net (Kaz Kylheku) writes:
>
> > cesur...@verizon.net (William D Clinger) wrote in message news:<fb74251e.03112...@posting.google.com>...
> > > Nils Goesche asked:
> > > > You mean, you really believe you need a computer to find out whether
> > > > 100! is prime?
> > >
> > > Hey, 2! is a prime. Why shouldn't there be others?
> >
> > I've never been able to overcome my amazement that 10!, 11! ... are
> > all divisible by 10. The list of zero digits grows, too as you get
> > past 100!, 1000! and so on. It's just friggin' amazing how these
> > factorials are such damn round numbers in the decimal system. That
> > kind of goes to show ya that there is, like, more to this base ten
> > thing than just the number of fingers on the human hand!
>
> But all factorials are figgin' amazingly damn round numbers in ALL bases!
Oops, not ALL bases, only all bases less than (sqrt (fact n)).
Kaz Kylheku
> k...@ashi.footprints.net (Kaz Kylheku) writes:
>
> > cesur...@verizon.net (William D Clinger) wrote in message news:<fb74251e.03112...@posting.google.com>...
> > > Nils Goesche asked:
> > > > You mean, you really believe you need a computer to find out whether
> > > > 100! is prime?
> > >
> > > Hey, 2! is a prime. Why shouldn't there be others?
> >
> > I've never been able to overcome my amazement that 10!, 11! ... are
> > all divisible by 10. The list of zero digits grows, too as you get
> > past 100!, 1000! and so on. It's just friggin' amazing how these
> > factorials are such damn round numbers in the decimal system. That
> > kind of goes to show ya that there is, like, more to this base ten
> > thing than just the number of fingers on the human hand!
>
> But all factorials are figgin' amazingly damn round numbers in ALL bases!
ALL YOUR BASE ARE BELONG TO US FACTORIALS!
/me *ducks*
(You practically begged for that one!)
larry
> I tried (sqrt (factorial 100)) when I wrote a function to determine if
> 100! is prime. I wrote a function 'factorial' to calculate 100! and
> anothor, 'prime', to check if a number x is prime. Originally I have a
> list in the function 'prime':
>
Check out this site for an algorithm for taking INTEGER square roots
http://www.embedded.com/98/9802fe2.htm
Joe Marshall
>
> ALL YOUR BASE ARE BELONG TO US FACTORIALS!
>
WHAT YOU SAY?
--
~jrm
Jason Sewall
square root if you asked for it - as the routine says, it's not exact.
Even so, I was being careless about the # of bits that are devoted to
the exponent.
Jason
Anthony Ventimiglia
Wow look at this this factorial thing seems to transcend the whole
idea of number bases.
[6]> (loop for base from 2 to 16 do
(setq *print-base* base)
(format t "BASE ~D: ~A~%" base (! 50)))
BASE 2: 10010011110111010111100100101100001111011010010011110011011000000101011000111101111010011110010100011010001100110101000010011110101100101110011101000011101001011000111100000000000000000000000000000000000000000000000
BASE 3: 1011211212111112122111101011000021010101102220102001111100211212110021211121200100101120211101212220100010001122210000000000000000000000
BASE 4: 102132322330211201323102132123000223013233103302203101212220103311211303220131023013200000000000000000000000
BASE 5: 122311134030022431034344000200304133201130202010401213040203141000143003314212102000000000000
BASE 6: 44211225441135530553445424500100412455345042334110200202001440000000000000000000000
BASE 7: 15416204032025314402166346053266444331652362065515024534513202515122100000000
BASE 8: 223672744541732236330053075723624321465023654563503513074000000000000000
BASE 9: 34755445574334007111386361440755407747610346741786303048700000000000
BASE 10: 30414093201713378043612608166064768844377641568960512000000000000
BASE 11: 909850787136088289093722148593009968A200464068522900946A0A0000
BASE 12: 65885466309B7A23721AA6B8A041A3727975340000000000000000000000
BASE 13: 99712988235066A0639436A28ABC038801B419899274631794A0B17000
BASE 14: 1DCDB2D20993ADD4308375B29829D94D171B7D675268110D200000000
BASE 15: 964E7D8B28BD67817BCE26D4198754AA6A4833B644C000000000000
BASE 16: 49EEBC961ED279B02B1EF4F28D19A84F5973A1D2C7800000000000
--
(incf *yankees-world-series-losses*)
Bruce Hoult
Jason Sewall <m...@me.com> wrote:
> Seriously, man, I can think of like 100 different factors for 100!
Really? Hmm ... I can only think of about 2^99 of them (less a few
duplicates).
-- Bruce
Bruce Hoult
k...@ashi.footprints.net (Kaz Kylheku) wrote:
Except that it works the same in any base.
But how *many* zeroes are there in N!?
Interestingly I was asked that question in a high school math quiz. And
even got it right! The answer is floor(N/5) + floor(N/25) +
floor(N/125) + floor(N/625) ...
So 100! has 20 + 4 + 0 + 0... = 24 zeros on the end.
-- Bruce
larry
ends with a lot of zeros in any base aren't you?
A number x written in base b ends with a zero if b is a factor of x.
For example 6 is divisble by 2 so it must end in zero in base 2.
Yes 6 in base 2 is 110. And in fact the number of zeros that a number
ends with in base b
is the number of times that b divides the number.
So 100! ends with a lot of zeros because there are many factors of 10
in 100!
All the numbers with 2 and or 5 as factors in 1,2,3,...100 combine to
give lots of factors of 10 and so lots of zeros at the end of the
number in base 10.
Similarly in base 2, all the numbers 1,2,3,...100 with factors of 2 to
combine to give lots
of factors of 2 and hence lots of zeros in base 2
Anthony Ventimiglia <anthony.at.vent...@spam.dev.null> wrote in message news:<87znelg...@afghan.dogpound>...
Joe Marshall
Joe Marshall
> You guys are just kidding right when you say you're amazed that n!
> ends with a lot of zeros in any base aren't you?
We're easily amused.
--
~jrm
Gareth McCaughan
Rather a lot of duplicates.
(defun factorial-exponent (n p)
"Biggest k such that p^k | n!."
(loop for x = (floor n p) then (floor x p) until (zerop x) sum x))
(defun primes-up-to (n)
"List of primes <= n."
(loop for i from 2 to n when (primep i) collect i))
(defun primep (n)
"True iff n is prime."
(loop for i from 2 to (isqrt n) do
(when (zerop (mod n i)) (return-from primep nil))) t)
(defun factorial-exponents (n)
"List of k such that p^k | n!, for all p making k>0."
(loop for p in (primes-up-to n) collect (factorial-exponent n p)))
(defun factorial-factors (n)
"Number of distinct positive integers dividing n!."
(let ((result 1))
(loop for m in (factorial-exponents n) do
(setf result (* result (1+ m))))
result))
(factorial-factors 100) => 39001250856960000
(ash 1 99) ==> 633825300114114700748351602688
--
Gareth McCaughan
.sig under construc
Bruce Hoult
Gareth McCaughan <gj...@g.local> wrote:
> Bruce Hoult <br...@hoult.org> writes:
>
> > In article <vs45355...@corp.supernews.com>,
> > Jason Sewall <m...@me.com> wrote:
> >
> > > Seriously, man, I can think of like 100 different factors for 100!
> >
> > Really? Hmm ... I can only think of about 2^99 of them (less a few
> > duplicates).
>
> Rather a lot of duplicates.
>
> [...]
>
> (factorial-factors 100) => 39001250856960000
> (ash 1 99) ==> 633825300114114700748351602688
OK, approx 2^55 (36028797018963968), then.
Still a better guess than 100 :-)
Btw, can I asume that everyone knows how to estimate the nearest power
of 2 to a number?
39001250856960000
~= 32 * 1000 * 1000 * 1000 * 1000 * 1000
5 10 10 10 10 10
~= 2 * 2 * 2 * 2 * 2 * 2
= 2^55
-- Bruce
Edward Huang
larry...@hotmail.com (larry) wrote in message news:<7b8f89d6.03112...@posting.google.com>...
William D Clinger
> > (ash 1 99) ==> 633825300114114700748351602688
>
> OK, approx 2^55 (36028797018963968), then.
>
> Still a better guess than 100 :-)
In the same spirit:
100 was a lot closer to the truth. It was off by only 2^55. :-)
Will
Raymond Toy
larry> s902...@ms5.pccu.edu.tw (Edward Huang) wrote in message news:<19297054.03112...@posting.google.com>...
>> Hi,
>> I tried (sqrt (factorial 100)) when I wrote a function to determine if
>> 100! is prime. I wrote a function 'factorial' to calculate 100! and
>> anothor, 'prime', to check if a number x is prime. Originally I have a
>> list in the function 'prime':
>>
larry> Check out this site for an algorithm for taking INTEGER square roots
larry> http://www.embedded.com/98/9802fe2.htm
The introduction was a turnoff:
Even with the best estimates, however, we can't predict in advance
how many iterations the method will take to converge to suitable
accuracy.
I think this is wrong.
But the final algorithm that's described is how I learned to do square
roots long ago in grade school.
Ray
Pascal Bourguignon
Almost:
[15]> (coerce (/ (ash 1 99) (factorial-factors 100)) 'float)
1.625141E13
[16]> (coerce (/ (factorial-factors 100) 100) 'float)
3.9001252E14
or:
[18]> (mapcar (lambda (x) (/ (log x) (log 2)))
(list (/ (ash 1 99) (factorial-factors 100))
(/ (factorial-factors 100) 100)))
(43.88563 48.470512)
100 was worse than 2^99, but not much.
10000 would be a better guess.
William D Clinger
methods in common use for computing the error in a guess:
; Off by a factor of...
(define (off-by-a-factor-of guess actual)
(max (/ guess actual)
(/ actual guess)))
; Off by...
(define (off-by guess actual)
(max (- guess actual)
(- actual guess)))
The first method (off-by-a-factor-of) essentially compares the
logarithms of the errors. By that method, 2^99 is a slightly
better guess than 100.
The second method (off-by) compares the absolute errors. By
that method, 100 is a far better guess than 2^99.
> (off-by-a-factor-of 100 39001250856960000)
390012508569600
> (round (off-by-a-factor-of (expt 2 99) 39001250856960000))
16251409536548
> (off-by 100 39001250856960000)
39001250856959900
> (off-by (expt 2 99) 39001250856960000)
633825300114075699497494642688
Will
Anthony Ventimiglia
> You guys are just kidding right when you say you're amazed that n!
> ends with a lot of zeros in any base aren't you?
Nothing slips by you does it ?
--
(incf *yankees-world-series-losses*)
Nils Goesche
> Err... In fact, I wanna know if 100!+1 is prime. (prime (! 100))
> is a test.
Well, you don't need a computer for that, either. 100! + 1 is
divisible by 101 by Wilson's theorem:
If p is a prime, then (p-1)! is congruent to -1 modulo p.
Take p = 101.
Regards,
--
Nils Gösche
"Don't ask for whom the <CTRL-G> tolls."
PGP key ID #xD26EF2A0
Michael Sullivan
> sqrt (coerce (factorial 100) 'double-float)) => 9.66054943799493E78
>
> The standard does not mandate that SQRT has to return an integer
> under any circumstances ("If number is a positive rational, it is
> implementation-dependent whether root is a rational or a float.")
It might be dependent on the number as well. I don't particularly want
my implementation thrashing around trying to come up with a rational in
response to (sqrt 2). The only way for such an action to make sense
would be if a precision were specified.
Michael
Joe Marshall
> s902...@ms5.pccu.edu.tw (Edward Huang) writes:
>
>> Err... In fact, I wanna know if 100!+1 is prime. (prime (! 100))
>> is a test.
>
> Well, you don't need a computer for that, either. 100! + 1 is
> divisible by 101 by Wilson's theorem:
I have a computer, but I don't have Wilson's theorem handy.
> If p is a prime, then (p-1)! is congruent to -1 modulo p.
>
> Take p = 101.
So this says take any prime number, subtract one, compute the
factorial, add one to that, and the result is divisible by the
original prime?
Ok, I think I see how that works.
Nils Goesche
> Nils Goesche <n...@cartan.de> writes:
>
>> s902...@ms5.pccu.edu.tw (Edward Huang) writes:
>>
>>> Err... In fact, I wanna know if 100!+1 is prime. (prime (! 100))
>>> is a test.
>>
>> Well, you don't need a computer for that, either. 100! + 1 is
>> divisible by 101 by Wilson's theorem:
>
> I have a computer, but I don't have Wilson's theorem handy.
Oh. Then I recommend getting "An Introduction to the Theory of
Numbers" by Hardy and Wright. Wonderful book, and everybody who can
remember at least some highschool mathematics can read it.
>> If p is a prime, then (p-1)! is congruent to -1 modulo p.
>>
>> Take p = 101.
>
> So this says take any prime number, subtract one, compute the
> factorial, add one to that, and the result is divisible by the
> original prime?
Yep.
larry
> larry...@hotmail.com (larry) writes:
>
> > You guys are just kidding right when you say you're amazed that n!
> > ends with a lot of zeros in any base aren't you?
>
> Nothing slips by you does it ?
Ouch ! You got me! That riposte was brilliant, absolutely brilliant:
"Nothing slips by you.."
I showed your comment to my friends and they just laughed and laughed.
'He's right," one of them said. One of my women friends wants to have
your baby so it can inherit some of your brilliance. But admit it, you
didn't come up with that brilliant comment on your own. Didn't Oscar
Wilde say it first?. If you did come up with it on your own then my
hat's off to your brilliance. You must have a lot of friends with that
wit of yours.
Thanks for putting me in my place. You are so smart and I am so dumb.
Joe Marshall
> Anthony Ventimiglia <anthony.at.vent...@spam.dev.null> wrote in message news:<87u14sg...@afghan.dogpound>...
>> larry...@hotmail.com (larry) writes:
>>
>> > You guys are just kidding right when you say you're amazed that n!
>> > ends with a lot of zeros in any base aren't you?
>>
>> Nothing slips by you does it ?
>
> Ouch ! You got me! That riposte was brilliant, absolutely brilliant:
> "Nothing slips by you.."
> I showed your comment to my friends and they just laughed and laughed.
> 'He's right," one of them said. One of my women friends wants to have
> your baby so it can inherit some of your brilliance.
Damn. I wish I had come up with that riposte.
--
~jrm
William D Clinger
bugging me ever since I posted it.
I wrote:
> The first method (off-by-a-factor-of) essentially compares the
> logarithms of the errors.
I should have written "compares the errors in the logarithms".
Will
Gareth McCaughan
> Oh. Then I recommend getting "An Introduction to the Theory of
> Numbers" by Hardy and Wright. Wonderful book, and everybody who can
> remember at least some highschool mathematics can read it.
It's a beautiful book indeed, but I think you're being
a little overoptimistic at the end there. I bought my
copy at age 15 or 16 or thereabouts, and there were bits
that I found *very* heavy going. At that point I could
certainly "remember at least some highschool mathematics" :-),
and I was better at it than most people who would describe
themselves that way...
Nils Gösche
Well, I didn't claim it was /easy/ to read :-) What I meant was that
you can read the book even if you haven't had ten courses in group
theory, abstract algebra and complex analysis already. This doesn't
mean it's a children's book, however: You have to be somewhat familiar
with mathematical thinking to be able to follow the arguments in that
book. As I am assuming that most people here have had some math
courses at college, it wouldn't be unreasonable to try, even if they
don't remember anything from their college courses.
Regards,
--
Nils Gösche
"Don't ask for whom the <CTRL-G> tolls."
PGP key ID #xEEFBA4AF
Edi Weitz
---------------------------------------------------^
> Gareth McCaughan <gj...@g.local> writes:
>
>> Nils Goesche wrote:
--------^
Looks like Nils has read the recent postings about RFC 2047... :)
Edi.
Nils Gösche
Heh, I did, actually. The reason I switched, though, is that I
realized that now, after years of misspelling it in ASCII, my very own
name looks unfamiliar to me when spelled correctly. I have decided to
reverse this process ;-)