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: 11 Dec 2008 08:08:38 pm Post subject: |
|
|
| Create a program that returns all the quadratic residues, modulo N. (No need to Prompt or Input for N, the value's already there.) The output should be a list in Ans, with no duplicates. |
|
| Back to top |
|
|
Weregoose
Authentic INTJ
Super Elite (Last Title)
Joined: 25 Nov 2004
Posts: 3976
|
| Posted: 11 Dec 2008 09:28:42 pm Post subject: |
|
|
| Going for sheer size, I have it in 42 bytes. |
|
| Back to top |
|
|
Ed H
Member
Joined: 30 Nov 2007
Posts: 138
|
| Posted: 12 Dec 2008 12:31:40 am Post subject: |
|
|
I have the same size.
What about optimizing for speed? What would be an efficient way to do this for large N?
One immediate optimization I can see is to only square the numbers from 1 to N/2, since (-a)2 = a2 (mod n). Beyond that you'd probably have to use number theory. |
|
| Back to top |
|
|
Weregoose
Authentic INTJ
Super Elite (Last Title)
Joined: 25 Nov 2004
Posts: 3976
|
| Posted: 12 Dec 2008 12:52:58 am Post subject: |
|
|
Ed H wrote: One immediate optimization I can see is to only square the numbers from 1 to N/2, since (-a)2 = a2 (mod n). Beyond that you'd probably have to use number theory. Then you know as much as I do. In fact, I speculate that coming up with a formula for the lengths of these lists might even make headway into an orderly enumeration of the primes.
As for our programs being the same size, the results of past challenges have led me to wonder whether we really did hit upon the same routine. But, there's time yet for more results, I think. 
Last edited by Guest on 12 Dec 2008 12:55:27 am; edited 1 time in total |
|
| Back to top |
|
|
Weregoose
Authentic INTJ
Super Elite (Last Title)
Joined: 25 Nov 2004
Posts: 3976
|
| Posted: 14 Dec 2008 04:46:34 pm Post subject: |
|
|
| Three days later... Time enough for results, or should we wait a week? |
|
| Back to top |
|
|
simplethinker
snjwffl
Active Member
Joined: 25 Jul 2006
Posts: 700
|
| Posted: 14 Dec 2008 07:16:03 pm Post subject: |
|
|
| I have 44 bytes. It's a simple routine, but it works. |
|
| Back to top |
|
|
Ed H
Member
Joined: 30 Nov 2007
Posts: 138
|
| Posted: 14 Dec 2008 07:55:15 pm Post subject: |
|
|
3 solutions seems enough.
Here is mine:
Quote: [font="courier new"]:{0
:For(X,1,N
:If min(Ans≠NfPart(X2/N
:augment(Ans,{NfPart(X2/N
:End
|
|
| Back to top |
|
|
Weregoose
Authentic INTJ
Super Elite (Last Title)
Joined: 25 Nov 2004
Posts: 3976
|
| Posted: 14 Dec 2008 09:55:42 pm Post subject: |
|
|
Well, Ed H posted my solution for me, except that I had used A instead of X. 
Last edited by Guest on 12 Jul 2010 01:43:16 am; edited 1 time in total |
|
| Back to top |
|
|
simplethinker
snjwffl
Active Member
Joined: 25 Jul 2006
Posts: 700
|
| Posted: 14 Dec 2008 09:57:46 pm Post subject: |
|
|
| Mine was the same, except instead of min(Ans≠... I had not(max(Ans=... (and I used A). |
|
| Back to top |
|
|
Ed H
Member
Joined: 30 Nov 2007
Posts: 138
|
| Posted: 15 Dec 2008 12:31:08 am Post subject: |
|
|
| Ah yes, De Morgan's laws. Those are useful to remember when optimizing. |
|
| 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
