Liberty BASIC Community Forum
« [RC] Left factorials »

Welcome Guest. Please Login or Register.
Jan 22nd, 2018, 6:06pm


Rules|Home|Help|Search|Recent Posts|Notification


« Previous Topic | Next Topic »
Pages: 1  Notify Send Topic Print
 sticky  Author  Topic: [RC] Left factorials  (Read 526 times)
tsh73
Moderator
ImageImageImageImageImage


member is offline

Avatar

Anatoly (real name)


PM

Gender: Male
Posts: 1732
xx [RC] Left factorials
« Thread started on: Jun 30th, 2015, 2:22pm »

[RC] Left factorials
Quote:
Left factorials, !n, may refer to (...)
This Rosetta Code task will be using this formula for left factorial:
!n = \sum_{k=0}^{n-1} k!
User Image
where
!0 = 0

Task

Display the left factorials for:
zero through ten (inclusive)
20 through 110 (inclusive) by tens

Display the length (in decimal digits) of the left factorials for:
1,000, 2,000 through 10,000 (inclusive), by thousands.


I admit C# "faster version" gave me some ideas as LB halted at !1000 of my first version ;)

Code:
'[RC] Left factorials
'defined as
'!n = \sum_{k=0}^{n-1} k!
'where !0 = 0

for i = 0 to 10
    print i, leftFact(i)
next
print
for i = 20 to 110 step 10
    print i, leftFact(i)
next
print
for i = 1000 to 10000 step 1000
    print i, len(str$(leftFact(i)))
next

function leftFact(n)
    if n = 0 then exit function
    leftFact = 1
    fact=1
    for k = 1 to n-1
        fact = fact*k
        leftFact = leftFact + fact
    next
end function
 

Output:
Code:
0             0
1             1
2             2
3             4
4             10
5             34
6             154
7             874
8             5914
9             46234
10            409114

20            128425485935180314
30            9157958657951075573395300940314
40            20935051082417771847631371547939998232420940314
50            620960027832821612639424806694551108812720525606160920420940314
60            141074930726669571000530822087000522211656242116439949000980378746128920420940314
70            173639511802987526699717162409282876065556519849603157850853034644815111221599509216528920420940314
80            906089587987695346534516804650290637694024830011956365184327674619752094289696314882008531991840922336528920420940314
90            16695570072624210767034167688394623360733515163575864136345910335924039962404869510225723072235842668787507993136908442336528920420940314
100           942786239765826579160595268206839381354754349601050974345395410407078230249590414458830117442618180732911203520208889371641659121356556442336528920420940314
110           145722981061585297004706728001906071948635199234860720988658042536179281328615541936083296163475394237524337422204397431927131629058103519228197429698252556442336528920420940314

1000          2565
2000          5733
3000          9128
4000          12670
5000          16322
6000          20062
7000          23875
8000          27749
9000          31678
10000         35656
 

« Last Edit: Jun 30th, 2015, 2:27pm by tsh73 » User IP Logged

damned Dog in the Manger
tsh73
Moderator
ImageImageImageImageImage


member is offline

Avatar

Anatoly (real name)


PM

Gender: Male
Posts: 1732
xx Re: [RC] Left factorials
« Reply #1 on: Jul 2nd, 2015, 05:34am »

Just want to say.
We got really lazy with fast computers and things like long integer support.
Last number printed - length of !10000 - actually involved computing 35656-digit number.

But last part of the task
Quote:
Display the length (in decimal digits) of the left factorials for:
1,000, 2,000 through 10,000 (inclusive), by thousands.

could be done faster and without long integers.

Her's how.
We asked for a length of a number.
Length of a number N could be calculated as
int(log10(N))+1
(and log10 could be calculated as log(N)/log(10))
Now, our number is actually sum of factorials of numbers <N, N above 1000
So. last (bigger) things in that sum differs in 1000's.
That means that number of digits is defined with that last item, that is, (N-1)!.
Now, main feature of LOG() function is that
LOG(a*b)=LOG(a)+LOG(b)
So we can calculate LOG((N-1)!) in pretty small numbers.

Here we are,
Code:
for i = 1000 to 10000 step 1000
    print i, lenFact(i-1)
next

function lenFact(n)
    logFact=0
    for i = 1 to n
        logFact=logFact+log(i)
    next
    lenFact = int(logFact/log(10))+1
end function
 

with same result.
Code:
1000          2565
2000          5733
3000          9128
4000          12670
5000          16322
6000          20062
7000          23875
8000          27749
9000          31678
10000         35656
 
« Last Edit: Jul 2nd, 2015, 05:35am by tsh73 » User IP Logged

damned Dog in the Manger
Pages: 1  Notify Send Topic Print
« Previous Topic | Next Topic »

Rules|Home|Help|Search|Recent Posts|Notification

Donate $6.99 for 50,000 Ad-Free Pageviews!

| |

This forum powered for FREE by Conforums ©
Sign up for your own Free Message Board today!
Terms of Service | Privacy Policy | Conforums Support | Parental Controls