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

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 )

* 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:
AADJUST.8xp
Code:
ACOMPARE.8xp
Code:
ADIVIDE.8xp
Code:

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:


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

edit:
Code:
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:
AADJUST.8xp
Code:
ACOMPARE.8xp
Code:
ADIVIDE.8xp
Code:

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:


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.

Tested, and I am not at risk of the numbers getting too high until well after the memory limit . 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:
AADJUST.8xp
Code:
ACOMPARE.8xp
Code:

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:

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.

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:


Hopefully you can understand the pseudocode, let alone implement it. It took forever to get down for me

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

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.

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.

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.