...on my TI-83+ series of calculators. Graphing Calculator

Not to worry, though, Jeremy Gibbons and I have a solution for you!

EDIT: We also have a WAY better solution here

Based on the findings in this mathematical paper, here is a TI-BASIC program that calculates one by one the digits of pi, with features such as:
    * Arbitrary precision arithmetic simulated through lists
    * An efficient decimal digit streaming algorithm
    * Adequately optimized code (will optimize more, though)
    * Author-verified to calculate more digits than he knows (and I know 100 Laughing )
    * insert other stuff here


At the current point, this isn't very user friendly. It is set in the program how many digits it computes. This may change soon.

Download links right here. Download every one of those files.

Code is as follows (there are 3 subprograms).

PICALC.8xp
Code:
{1→ʟQ
{180→ʟR
{60→ʟT
2→I
ClrHome
501→D
"CHANGE THE ABOVE NUMBER TO CALCULATE MORE OR LESS DIGITS
"?→Str1
For(J,1,D
Output(1,1,Str1
Output(8,1,J
"ABOVE FOR TESTING
3(3I+1)(3I+2→U
5ʟT→L1
prgmAADJUST
L1→L3
5ʟR→L1
prgmAADJUST
L1→L2
(27I-12)ʟQ→L1
prgmAADJUST
L1+L2→L1
prgmAADJUST
L3→L2
prgmADIVIDE
θ→Y
Str1+sub("0123456789",Y+1,1→Str1
(5I-2)ʟQ→L1
prgmAADJUST
L1→L2
YʟT→L1
prgmAADJUST
L2-L1+ʟR→L1
prgmAADJUST
10UL1→L1
prgmAADJUST
L1→ʟR
10I(2I-1)ʟQ→L1
prgmAADJUST
L1→ʟQ
UʟT→L1
prgmAADJUST
L1→ʟT
I+1→I
End
AADJUST.8xp
Code:
DelVar BDelVar C1→A
Repeat B or A>dim(L1
C+L1(A→L1(A
If not(Ans
A=dim(L1)+1-sum(int(1/(1+cumSum(abs(seq(L1(Z),Z,dim(L1),1,-1→B
int(10^(7)⁻¹Ans→C
If 0>L1(A
-10^(7)Ans+L1(A→L1(A
10^(7)fPart(10^(7)⁻¹L1(A→L1(A
A+1→A
If C and Ans>dim(L1
Then
0→L1(A
1+dim(ʟQ→dim(ʟQ
Ans→dim(ʟR
Ans→dim(ʟT
Ans→dim(L2
Ans→dim(L3
End
End
ACOMPARE.8xp
Code:
DelVar Gdim(L1→A
Repeat G or A<1
(L1(A)>L2(A))-(L1(A)<L2(A→G
A-1→A
End
ADIVIDE.8xp
Code:
DelVar θprgmACOMPARE
While G≥0
Output(6,1,"
Output(6,1,θ
"ABOVE FOR TESTING
L1-L2→L1
prgmAADJUST
θ+1→θ
prgmACOMPARE
End
Nice idea! I've seen a couple of list-based arbitrary-precision arithmetic BASIC programs for the z80 calcs, and I'm not sure where this falls on the scale of efficiency.

-Are you using a single digit per list element, or multiple? It looks like one to me, but I want to make sure...
-Is prgmAADJUST carrying the digits in L1?
-I see from looking at ACOMPARE that the list elements seem to be stored from left to right in increasing place value, that is 3.14159 would be {9,5,1,4,1,3}. Is this correct?

I'll take a closer look at it soon.
lirtosiast wrote:
Nice idea! I've seen a couple of list-based arbitrary-precision arithmetic BASIC programs for the z80 calcs, and I'm not sure where this falls on the scale of efficiency.

-Are you using a single digit per list element, or multiple? It looks like one to me, but I want to make sure...
-Is prgmAADJUST carrying the digits in L1?
-I see from looking at ACOMPARE that the list elements seem to be stored from left to right in increasing place value, that is 3.14159 would be {9,5,1,4,1,3}. Is this correct?

I'll take a closer look at it soon.

1. I use 7 digits per element.
2. Yes, that is the function of AADJUST. Such as ACOMPARE compares two lists stored in L1 and L2 (used in ADIVIDE), and ADIVIDE performs division by repeated subtraction on two lists stored in L1 and L2.
3. ...the numbers do not represent decimals. They represent only integers. My algorithm only uses integer math, and the result of the division (the only point in the program where I use ADIVIDE) is the next pi digit. But yeah, you're right in that it stores from left to right in increasing place value, i.e. 12345678901234567890 would be {4567890,7890123,123456}.

As for efficiency, I've tried to make some speed optimizations to the programs. For example, I made the numbers 1 list element long at first, and add more only when necessary. For AADJUST, I automatically make it end when it reaches a point where there is no carry and all the rest of the digits are 0s. etc.

I left this code running for 6 hours, and it gave me 150 digits. It gets a lot slower when a lot of digits have been calculated. And I mean a LOT. If anyone could help speed up the code, it would be greatly appreciated.
This should work for carrying:

Code:
0→C
For(A,1,dim(L₁
L₁(A)+C→X
int(Ansᴇ-7→C
X-Ansᴇ7→L₁(A)
End
If C
C→L₁(A


Can be optimized further using finance variables (for example, n for A and N for X, or something like that).

edit:

Code:
tanh(E9imag(max(i(cumsum(1 or L1)tanh(E9(L1-L2
gives +1 if the number represented by L1 is greater, -1 if L2 is greater, and 0 if the lists are equal. L1 and L2 must be the same size. If you just want positive/0/negative rather than 1/0/-1 you can remove the initial tanh(E9.
This routine is O(n) rather than O(1) in the list size but it will be much faster for small n. The parenthesis after i is intentional as I think it makes multiplication faster.
edit: Welp, looks like it wasn't faster after all.
Thanks for the improvements, lirtosiast. I also came up with some trivial improvements of my own, and I'll post them later today.
I have new code! With this one, I tested that the maximum amount of digits it can supply on a fully RAM cleared calculator is 377, and this is done so in 3 hours 45 minutes. (don't worry, it doesn't go at the speed of 1.675 minutes per digit...it just gets slower with digits calculated, as expected)

Download links right here. Download all those files.

Code is as follows:

PICALC.8xp
Code:
SetUpEditor Q,T,R
{1->|LQ
{60->|LT
3Ans->|LR
ClrHome
377->D
"?->Str1
For(J,2,D+1
Output(1,1,Str1
Output(6,1,"
Output(8,1,J-1
5|LT->L1
prgmAADJUST
L1->L2
(27J-12)|LQ+5|LR->L1
prgmAADJUST
prgmADIVIDE
Str1+sub("0123456789",theta+1,1->Str1
30((5J-2)|LQ-theta|LT+|LR->L1
prgmAADJUST
(3J+1)L1->L1
prgmAADJUST
(3J+2)L1->L1
prgmAADJUST
L1->|LR
10J(2J-1)|LQ->L1
prgmAADJUST
L1->|LQ
3(3J+1)|LT->L1
prgmAADJUST
(3J+2)L1->L1
prgmAADJUST
L1->|LT
End
AADJUST.8xp
Code:
DelVar C
For([recursiven],1,dim(L1
C+L1([recursiven]->|N
int(Ans|E~7->C
|N-Ans|E7->L1([recursiven]
End
If C
C->L1([recursiven]
dim(L1->dim(L2
Ans->dim(|LQ
Ans->dim(|LR
Ans->dim(|LT
ACOMPARE.8xp
Code:
1+dim(L1->A
Repeat Ans or A<2
A-1->A
(L1(A)>L2(A))-(L1(A)<L2(A
End
ADIVIDE.8xp
Code:
DelVar thetaprgmACOMPARE
While Ans>=0
Output(6,1,"
Output(6,1,theta
L1-L2->L1
prgmAADJUST
theta+1->theta
prgmACOMPARE
End
Good job optimizing! I have two questions: first, it doesn't appear you are at risk of having more than one carry during the (3J+1)(3J+2) multiplying step. Have you tested without the intermediate AADJUST?

Second, have you thought about starting ADIVIDE with a check to see if L1 is more than 5L2, so you only need to compare ~3 times on average rather than 5?

Also,

Code:
If C 
C->L1(n

//can be (bc dims don't change anywhere else)
If not(C
Return
C->L1(n

(L1(A)>L2(A))-(L1(A)<L2(A

//can be, I think,
L1(A)-L2(A


EDIT: Position of the last nonzero element of L1 is max((0 xor L1)cumSum(1 or L1. The last occurrence of X is max((L1=X)cumsum(1 or L1. I don't know why I couldn't think of it earlier. I don't think it'll be any faster than the current comparing method, though.
lirtosiast wrote:
Good job optimizing! I have two questions: first, it doesn't appear you are at risk of having more than one carry during the (3J+1)(3J+2) multiplying step. Have you tested without the intermediate AADJUST?

Second, have you thought about starting ADIVIDE with a check to see if L1 is more than 5L2, so you only need to compare ~3 times on average rather than 5?

Also,


Code:
If C 
C->L1(n

//can be (bc dims don't change anywhere else)
If not(C
Return
C->L1(n

(L1(A)>L2(A))-(L1(A)<L2(A

//can be, I think,
L1(A)-L2(A

Tested, and I am not at risk of the numbers getting too high until well after the memory limit Razz . But I'm not sure I can go without a carry at most points.

And I have not thought of that...but I'm not sure how to do that without changing L1 or L2. In fact, I don't know any other division algorithm besides repeated subtraction that can work. I don't suppose some other person who has designed an arithmetic system like this has another more efficient algorithm for integer division? *cough*Spartacus*cough*
Bump.

Even newer code. Now, no divide program. Also a bit faster.

Download links here (download all of those files), here is the code to type in:

PICALC.8xp
Code:
SetUpEditor Q,T,R
{1->|LQ
{60->|LT
3Ans->|LR
ClrHome
Output(7,1,"CLEAR TO EXIT.  #    NEXT: 0...
"?->Str1
2->I%
Repeat getKey=45
If 1<length(Str1
Then
"   
If not(fPart((length(Str1)-2)/16
Output(6,1,Ans+Ans+Ans+Ans
2+16int((length(Str1)-82)/16)(98<=length(Str1
Output(1,1,sub(Str1,Ans,length(Str1)+1-Ans
End
Output(8,2,I%-2
Output(8,12,0
5|LT->L1
prgmAADJUST
L1->L2
(9I%-4)|LQ->L1
prgmAADJUST
3L1+5|LR->L1
prgmAADJUST
0->PV
prgmACOMPARE
While Ans>=0
PV+1->PV
Output(8,12,PV
L1-L2->L1
prgmAADJUST
prgmACOMPARE
End
sub("0123456789",PV+1,1
If I%=2
Ans+".
Str1+Ans->Str1
(5I%-2)|LQ+|LR-PV|LT->L1
prgmAADJUST
30L1->L1
prgmAADJUST
If I%<33
Then
9I%^^2+9I%+2
Else
(3I%+1)L1->L1
prgmAADJUST
3I%+2
End
AnsL1->L1
prgmAADJUST
L1->|LR
10I%|LQ->L1
prgmAADJUST
(2I%-1)L1->L1
prgmAADJUST
L1->|LQ
3|LT->L1
prgmAADJUST
If I%<33
Then
9I%^^2+9I%+2
Else
(3I%+1)L1->L1
prgmAADJUST
3I%+2
End
AnsL1->L1
prgmAADJUST
L1->|LT
I%+1->I%
End
ClrHome
sub(Str1,2,length(Str1)-1->Str1
Disp "# OF DIGITS:","DIGITS STORED IN","Str1
Output(1,14,I%-2
AADJUST.8xp
Code:
If min(L1)>0 and |E10>=max(L1
Return
0->PMT
For([recursiven],1,dim(L1
PMT+L1([recursiven]->|N
int(|N|E~10->PMT
|N-PMT|E10->L1([recursiven]
End
If not(PMT
Return
[recursiven]->dim(L2
Ans->dim(|LQ
Ans->dim(|LR
Ans->dim(|LT
PMT->L1(Ans
ACOMPARE.8xp
Code:
1+dim(L1->|N
Repeat Ans or |N=1
|N-1->|N
L1(|N)-L2(|N
End
Here's a Pi program that I originally wrote for my iPad. I modified it to run on my TI 84 Plus SE. I must have an earlier TI 84 version because I don't have a mod function so I had to improvise with iPart. The program will print 7 digits for each iteration after the decimal point. If there are only 6 digits showing, then there should be a leading 0 where the space is. Below are the digits and times that I tried. The max is 999 digits which I haven't tried. I estimate it will take about 5000 seconds. If I run the code on my iPad, it will do 100,000 digits in 420 seconds. For 400 digits, it takes only .009 seconds.

Digits Seconds
10 -- 1
20 -- 4
40 -- 14
80 -- 49
160 -- 178
400 -- 1097


Code:

ClrHome
Input "NBR DIGITS ",D
startTmr->Q
iPart(D/7)+1->S
10^7->T
For(Z,1,D
5*(Z-1)+3->L1(Z
End
For(M,1,S
0->C
For(Z,D,1,-1
L1(Z)*T+C->V
27*((Z-1)^2)+27*(Z-1)+6->B
V-iPart(V/B)*B->L1(Z
iPart(V/B)*(2*((Z-1)^2)-(Z-1))->C
End
V-iPart(V/T)*T->L1(1
Disp iPart(V/T
End
Disp "SECONDS "
checkTmr(Q)
dave1707 wrote:
I must have an earlier TI 84 version because I don't have a mod function so I had to improvise with iPart.


The remainder( function comes with the 2.53MP and 2.55MP operating systems, it isn't tied to the calculator hardware. You can download the latest operating system here, and install it with TI Connect CE if you have a link cable. If you want to upgrade your operating system, make sure that all of your programs are Archived or Grouped first, and preferably backed up to the computer.

I have compared the speed of remainder(A,B) to BfPart(A/B) before, and remainder( is significantly faster, although I don't remember exactly how much.
dave1707, I'm impressed! This seems to calculate faster than mine per iteration, and 7 digits per iteration at that! What's the algorithm behind this? Can I get a mathematical reference or something about this?

Also, yours seems like it needs to allocate memory beforehand for a certain number of digits to calculate. I originally created my program to circumvent this, as my algorithm goes on forever calculating digits simply until you tell it to stop. Could this program be modified to go on infinitely until it is terminated?

Oh, and one thing about programming on the calculator is that the numbers only reach 14 digits before some accuracy is lost. What is the maximum number of digits that a number reaches in the process of this algorithm?
JWinslow23 It uses a Pi Spigot, see this link, http://www.pi314.net/eng/goutte.php , scroll down to other formula. It does need to allocate table memory in advance. The algorithm shown in the link is for a single digit at a time, but I modified mine to do 7 digits. I'm not sure at what point it will overflow, but the list limit is 999 entries on the TI 84. As I said in my other post, on my iPad I've done 100,000 digit without problems and that uses 64 bit math routines which is probably 14 digits or so. Maybe I'll look at your routine and see if I can convert it to Lua and try it on my iPad. I'm not very good at TI Basic, so if you have your program in English type pseudo code, maybe that would be easier to convert.
dave1707 wrote:
JWinslow23 It uses a Pi Spigot, see this link, http://www.pi314.net/eng/goutte.php , scroll down to other formula. It does need to allocate table memory in advance. The algorithm shown in the link is for a single digit at a time, but I modified mine to do 7 digits. I'm not sure at what point it will overflow, but the list limit is 999 entries on the TI 84. As I said in my other post, on my iPad I've done 100,000 digit without problems and that uses 64 bit math routines which is probably 14 digits or so. Maybe I'll look at your routine and see if I can convert it to Lua and try it on my iPad. I'm not very good at TI Basic, so if you have your program in English type pseudo code, maybe that would be easier to convert.

Oh yeah, I believe I've heard of that very algorithm. It's actually a very useful one. Nice, didn't recognize it at first.

The algorithm I based my program off of is also a spigot, but it's a "true" spigot; if you run it, say, 100 times, you get 100 digits. It needs to use arbitrarily-sized integers, similar to Java's BigInteger type, as the numbers get really big really fast. I simulated this in TI-BASIC with lists of numbers that are 11 digits long (any longer, and the required math would reduce the accuracy of the numbers).

Here's some pseudocode (Q, R, T, and U need to be BigInts):


Code:
Let Q = 1
Let R = 180
Let T = 60
Let I = 2
Repeat until user-terminated
  Let N = int( (5T) / ((27I - 12)Q + 5R) )
  Give N as next digit
  Let U = 3(3I + 1)(3I + 2)
  Let R = 10U((5I-2)Q + R - NT)
  Let Q = 10QI(2I - 1)
  Let T = UT
  Let I = I + 1
EndRepeat


Hopefully you can understand the pseudocode, let alone implement it. It took forever to get down for me Razz
JWinslow23 Here's what I think. I added the * for multiplication.
Does the N=int mean that N = the integer part of the whole division. It looks like it comes up always 0.
Not sure what give N as next digit means.
I was just doing 5 iterations to start with.

Q = 1
R = 180
T = 60
I = 2
for z=1,5 do -- just do 5 iterations
N = int((5*T)/((27*I-12)*Q + 5*R)) -- does int mean integer part of division
give N as next digit -- not sure what this means ( print N ? )
U = 3*(3*I+1)*(3*I+2)
R = 10*U*((5*I-2)*Q+R-N*T)
Q = 10*Q*I*(2*I-1)
T = U*T
I = I+1
end
Quote:
N = int((5*T)/((27*I-12)*Q + 5*R)) -- does int mean integer part of division

Yes; it's a TI-BASIC command meaning "the largest whole number less than or equal to X", which is equivalent to iPart() for positive arguments.
Quote:
give N as next digit -- not sure what this means ( print N ? )

After that division, N is actually the next decimal digit. You can print it here if you want to see a running tally, yes.

And you grouped everything right, too.
Doing the first iteration, I get for N the value 0.31847133757962 . The next digit is 3 which is the correct value for Pi so far. But if N is supposed to be the iPart, then that makes N a value of 0 . Then all the next iterations, N is even smaller and results in a 0. Maybe I'm doing something wrong.
dave1707 wrote:
Doing the first iteration, I get for N the value 0.31847133757962 . The next digit is 3 which is the correct value for Pi so far. But if N is supposed to be the iPart, then that makes N a value of 0 . Then all the next iterations, N is even smaller and results in a 0. Maybe I'm doing something wrong.

Whoops, I did something wrong. The numerator and denominator of the division are supposed to be switched. It's N = int(((27*I-12)*Q + 5*R) / (5*T)) .
That works a lot better. I get 3.14159 before I start getting bad values because of overflow calculations. I guess I'll start looking into doing big number calculations.
JWinslow23 Maybe I won't try to figure out big number calculations. You said that calculating 377 digits would use up all the RAM. I can calculate 999 digits without using much RAM, just the limit of a list (table) variable. I could probably increase the digits by combining a second, third, or fourth list (table) variable. The only problem is the calculations are so slow that it wouldn't be feasible to do it. As for doing the calculations on my iPad, I might be able to go several million digits before I overflow the calculations. Again, it probably wouldn't be feasible to try it. Just creating the program is the interesting and fun part, not actually calculating the digits.

If I did my calculations right, I should be able to do about 2,000,000 digits on the iPad. As for the TI 84, it should be 999 digits times the number of list (table) variables that will fit in RAM if I could combine them as long as it's not more than 2,000 variables.
  
Register to Join the Conversation
Have your own thoughts to add to this or any other topic? Want to ask a question, offer a suggestion, share your own programs and projects, upload a file to the file archives, get help with calculator and computer programming, or simply chat with like-minded coders and tech and calculator enthusiasts via the site-wide AJAX SAX widget? Registration for a free Cemetech account only takes a minute.

» Go to Registration page
Page 1 of 2
» All times are UTC - 5 Hours
 
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum

 

Advertisement