Optmising BASIC code for A^K mod P

[Xeda112358]

I made this code to compute A^K 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

[jacobly]

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


[Xeda112358]

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!

[Deep Toaster]

Optimizing your original code:

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:

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.

[Xeda112358]

The problem with that is that it is quite a lot slower for larger values of K. The algorithm I posted takes ceiling(log₂K) 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.