This is an archived, read-only copy of the United-TI subforum , including posts and topic from May 2003 to April 2012. If you would like to discuss any of the topics in this forum, you can visit Cemetech's
TI-BASIC subforum. Some of these topics may also be directly-linked to active Cemetech topics. If you are a Cemetech member with a linked United-TI account, you can link United-TI topics here with your current Cemetech topics.
TI-Basic Brain Teasers =>
TI-BASIC
| Author |
Message |
|
Ed H
Member
Joined: 30 Nov 2007
Posts: 138
|
 Posted: 30 Sep 2008 12:31:51 am Post subject: |
|
|
Write a program that takes three inputs, a base B, an exponent E, and a modulus M, and returns the value of B^E (mod M).
One restraint is that the program cannot actually multiply B E times; it must be fast enough for semi-practical use.
Last edited by Guest on 14 Oct 2008 10:03:15 pm; edited 1 time in total |
|
| Back to top |
|
|
Weregoose
Authentic INTJ
Super Elite (Last Title)
Joined: 25 Nov 2004
Posts: 3976
|
| Posted: 30 Sep 2008 02:40:08 am Post subject: |
|
|
| 67 bytes: Spoiler wrote: 1→A
For(I,1,[font="verdana"]E‾5+log(2E)/log(2
If int(2fPart(E/2^I
AB-Mint(AB/M→A
B²-Mint(B²/M→B
End
A
I have a hunch that this can be improved still, but it was necessary to keep updating B separately to keep it from overflowing...
Last edited by Guest on 30 Jul 2010 04:26:14 am; edited 1 time in total |
|
| Back to top |
|
|
Ed H
Member
Joined: 30 Nov 2007
Posts: 138
|
| Posted: 01 Oct 2008 10:44:28 pm Post subject: |
|
|
I got 56 bytes using the same algorithm. However, I used a while loop instead of a for loop. This is what I had:
Quote: 1→R
While E
If fPart(.5E
BR-Mint(BR/M→R
int(.5E→E
B²-Mint(B²/M→B
End
R
Other than the loop, our code is almost identical.
Edit: to give credit where it's due, I found the algorithm on the Wikipedia entry for modular exponentiation.
Last edited by Guest on 30 Jul 2010 04:22:28 am; edited 1 time in total |
|
| Back to top |
|
|
Weregoose
Authentic INTJ
Super Elite (Last Title)
Joined: 25 Nov 2004
Posts: 3976
|
| Posted: 05 Oct 2008 03:41:18 pm Post subject: |
|
|
Do you mind if I display that on my website? Once I can figure out a safe range of inputs...
Last edited by Guest on 05 Oct 2008 03:42:52 pm; edited 1 time in total |
|
| Back to top |
|
|
Ed H
Member
Joined: 30 Nov 2007
Posts: 138
|
| Posted: 05 Oct 2008 11:07:59 pm Post subject: |
|
|
I mind not at all.
I find that you're most likely to lose precision when the modulus is very high - I know E is good up to 2E13, and B is probably good up to around 10^7. |
|
| Back to top |
|
|
|
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
