Login [Register]
Don't have an account? Register now to chat, post, use our tools, and much more.
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.

This forum is locked: you cannot post, reply to, or edit 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. Smile


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. Razz

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
Display posts from previous:   
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
    »
» View previous topic :: View next topic  
Page 1 of 1 » All times are GMT - 5 Hours

 

Advertisement