### Author Topic: Optmising BASIC code for A^K mod P  (Read 2480 times)

0 Members and 1 Guest are viewing this topic.

#### Xeda112358

• they/them
• Moderator
• LV12 Extreme Poster (Next: 5000)
• Posts: 4675
• Rating: +718/-6
• Calc-u-lator, do doo doo do do do.
##### Optmising BASIC code for A^K mod P
« 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:EndI 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
« Last Edit: January 07, 2013, 12:51:19 pm by Xeda112358 »

#### jacobly

• Posts: 205
• Rating: +161/-1
##### Re: Optmising BASIC code for A^K mod P
« Reply #1 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,1While int(2Ans(1Ans{.5,Ans(2),1+(Ans(2)-1)int(2fPart(Ans(1Ans-Pint({0,1,1}Ans/PEndAns(3

#### Xeda112358

• they/them
• Moderator
• LV12 Extreme Poster (Next: 5000)
• Posts: 4675
• Rating: +718/-6
• Calc-u-lator, do doo doo do do do.
##### Re: Optmising BASIC code for A^K mod P
« Reply #2 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!

#### Deep Toaster

• So much to do, so much time, so little motivation
• LV13 Extreme Addict (Next: 9001)
• Posts: 8217
• Rating: +758/-15
##### Re: Optmising BASIC code for A^K mod P
« Reply #3 on: January 07, 2013, 02:05:09 pm »
Quote from: TI-BASIC
1→MWhile iPart(K.5K→KIf int(2fPart(AnsPfPart(AM/P→MPfPart(A2/P→AEnd
Slower time but half the size:
Quote from: TI-BASIC
1For(I,1,KPfPart(AAns/PEndround(Ans,0

EDIT: Corrected by Runer112—second one can be significantly slower because it's on a different time complexity.
« Last Edit: January 07, 2013, 11:47:52 pm by Deep Thought »

#### Xeda112358

• they/them
• Moderator
• LV12 Extreme Poster (Next: 5000)
• Posts: 4675
• Rating: +718/-6
• Calc-u-lator, do doo doo do do do.
##### Re: Optmising BASIC code for A^K mod P
« Reply #4 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.
« Last Edit: January 08, 2013, 12:06:15 am by Xeda112358 »