Omnimaga

Calculator Community => TI Calculators => TI-BASIC => Topic started by: Xeda112358 on January 07, 2013, 11:00:40 am

Title: Optmising BASIC code for A^K mod P
Post by: Xeda112358 on January 07, 2013, 11:00:40 am
I made this code to compute AK mod P and I was wondering if it could be optmised and still preserve the speediness (or make it faster).
Code: [Select]
:1→M
:While int(K
:.5K→K
:If int(2fPart(Ans
:AM-Pint(AM/P→M
:A²-Pint(A²/P→A
:End
I feel like it could be optimised in BASIC. And maybe use only three variables (base, exponent, mod).
EDIT: Optimised with suggestions from calc84maniac and Jacobly
EDIT2: Figured out that .5K is faster than K/2
Title: Re: Optmising BASIC code for A^K mod P
Post by: jacobly on January 07, 2013, 12:24:58 pm
I have no idea if this is faster, but it doesn't use M.

Code: [Select]
{.5K,A,1
While int(2Ans(1
Ans{.5,Ans(2),1+(Ans(2)-1)int(2fPart(Ans(1
Ans-Pint({0,1,1}Ans/P
End
Ans(3
Title: Re: Optmising BASIC code for A^K mod P
Post by: Xeda112358 on January 07, 2013, 12:31:07 pm
Wow, it isn't faster, but it is still pretty fast and only a few byte bigger than the code I had (excluding the first and last line). That is an awesome use of lists!
Title: Re: Optmising BASIC code for A^K mod P
Post by: Deep Toaster on January 07, 2013, 02:05:09 pm
Optimizing your original code:
Quote from: TI-BASIC
1→M
While iPart(K
.5K→K
If int(2fPart(Ans
PfPart(AM/P→M
PfPart(A2/P→A
End
Slower time but half the size:
Quote from: TI-BASIC
1
For(I,1,K
PfPart(AAns/P
End
round(Ans,0

EDIT: Corrected by Runer112—second one can be significantly slower because it's on a different time complexity.
Title: Re: Optmising BASIC code for A^K mod P
Post by: Xeda112358 on January 07, 2013, 11:52:42 pm
The problem with that is that it is quite a lot slower for larger values of K. The algorithm I posted takes ceiling(log2K) number of iterations compared to K iterations. For example, K=999 takes 10 iterations versus 999. At K=999999999, my code takes about 2 seconds, yours would take one or two years, if my estimations are correct o.o

In fact, that is very similar to the code I was trying to speed up (somebody posted an encryption program on TI|BD, and I knew the more efficient algorithm).
EDIT: Never mind, I thought you were quoting my code, I see now. The issue with the first optimisation is a rather bothersome one. I used to use the fPart( method, but that will cause rounding errors that mess up the mod() formula, especially with numbers with certain prime factors.