Author Topic: [TI-Planet Contest] Heat up your calc with arithmetic !  (Read 11711 times)

0 Members and 1 Guest are viewing this topic.

Offline Runer112

  • Moderator
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2289
  • Rating: +639/-31
    • View Profile
Re: [TI-Planet Contest] Heat up your calc with arithmetic !
« Reply #15 on: April 04, 2013, 09:39:05 pm »
I have multiple questions:

  • How large of numbers do we have to handle?
  • How will speed be measured? Does our algorithm need to be fast for small numbers, large numbers, or both? If both, does one matter more than the other?
  • Is there some limit on program size, or does size somehow factor into judging?
  • Can we use pre-calculated data that isn't a list of prime palindromes? And if so, is there a limit to what/how much we can use?
  • And a non-technical question, can we submit entries for multiple platforms/languages?

EDIT: One more question, can we store some prime palindromes as long as it's not just a straightforward list of them? If so, are there restrictions?
« Last Edit: April 04, 2013, 10:04:56 pm by Runer112 »

Offline Adriweb

  • Editor
  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1708
  • Rating: +229/-17
    • View Profile
    • TI-Planet.org
Re: [TI-Planet Contest] Heat up your calc with arithmetic !
« Reply #16 on: April 05, 2013, 02:25:58 am »
How large of numbers do we have to handle?[/li][/list]
We did not specify a specific range. We'll test against a number of values (positive integers), from small to bigger ones.

How will speed be measured? Does our algorithm need to be fast for small numbers, large numbers, or both? If both, does one matter more than the other?[/li][/list]
I guess we'll be measuring speed among the same kind of programs, by launching them with the same number, and measuring with a chronometer each one, from the "enter" key pressed to the end of the program. We'll do that, as said, for multiple numbers ranging from small to bigger ones.
About the second question, I guess it would have to work for both in order to have the maximum amount of points. But obviously, if your algorithm is the one (or one of the few) that really works well for big numbers, and relatively fast, well, that'll be good.

Is there some limit on program size, or does size somehow factor into judging?[/li][/list]
We did not specify any program size, since we'll mainly test against speed. However, a 1k (<- I just invented this size) program will probably have a better grade than a 10k one...

Can we use pre-calculated data that isn't a list of prime palindromes? And if so, is there a limit to what/how much we can use?[/li][/list]
There was discussion too about this on TI-Planet, what got out of that was that as long as it's mainly not a list of "things" (palindromes, directly, primes directly, or RLE-encoded things) that would be used to search through ( / parse / decode ) to directly give the answer for the requested number.

And a non-technical question, can we submit entries for multiple platforms/languages?[/li][/list]
Nope, sorry.

EDIT: One more question, can we store some prime palindromes as long as it's not just a straightforward list of them? If so, are there restrictions?
See my previous answer, I guess ?

Offline Adriweb

  • Editor
  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1708
  • Rating: +229/-17
    • View Profile
    • TI-Planet.org
Re: [TI-Planet Contest] Heat up your calc with arithmetic !
« Reply #17 on: April 05, 2013, 07:15:39 am »
I'm translating critor's post from TI-Planet ( http://tiplanet.org/forum/viewtopic.php?p=137928#p137928 )

Quote
Hello,

We have disccused yesterday evening about the issue [of asm/basic being judged the same way]

In the z80 category :
  • we receive valid ASM and Basic entries
  • the majority of ASM entries would yield faster results than Basic ones
So, we are ready to actually make it so there are 3 categories ((TI-Basic z80, Asm z80, TI-Nspire)), and so we add another TI-84 Pocket.fr to win.

That should appease your fear, and you should't worry any more about a possible unfairness, of course if we receive quality ASM entries.

A hybrid program (asm + basic) will be considered ASM.

For now, we only have received one entry, and we couldn't really compare anything.

Offline TIfanx1999

  • ಠ_ಠ ( ͡° ͜ʖ ͡°)
  • CoT Emeritus
  • LV13 Extreme Addict (Next: 9001)
  • *
  • Posts: 6173
  • Rating: +191/-9
    • View Profile
Re: [TI-Planet Contest] Heat up your calc with arithmetic !
« Reply #18 on: April 05, 2013, 07:27:09 am »
Thank you for all your answers. Sounds good! :)

Offline Runer112

  • Moderator
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2289
  • Rating: +639/-31
    • View Profile
Re: [TI-Planet Contest] Heat up your calc with arithmetic !
« Reply #19 on: April 05, 2013, 11:08:18 am »
About the size thing again, surely there must be some established limit? For instance, the Ans variable on the 82/83/84 can only store integers up to 14 digits without loss of information, so there has to be at least a hard limit for that. And chances are finding nth palindromes that are that long would take far too long anyways. It would also be helpful for assembly programmers to know a limit; it doesn't seem right to leave us in the dark in a speed competition, encouraging us to gamble on using smaller numbers for faster math. Someone may have an advantage just because they guessed the minimal number size that still works, and someone else's efforts may completely be wasted if they used numbers slightly too small and their program ended up not passing the tests at all.

Another follow-up question, can we get a bit more information about how scoring will work? I'm especially wondering about things like how speed for varying number sizes will be scored. How will the speed of assembly programs be compared for small values, considering they may complete the computation in a fraction of a second? And if one program uses a heavy but high-end-optimized algorithm that takes, say, 0.7 seconds, 2 seconds, 8 seconds, and 36 seconds on tests while another program that uses a lighter but less high-end-optimized algorithm takes 0.2 seconds, 0.7 seconds, 5 seconds, and 114 seconds for the same tests, which would win?

Offline Adriweb

  • Editor
  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1708
  • Rating: +229/-17
    • View Profile
    • TI-Planet.org
Re: [TI-Planet Contest] Heat up your calc with arithmetic !
« Reply #20 on: April 05, 2013, 11:50:25 am »
About the size thing again, surely there must be some established limit? For instance, the Ans variable on the 82/83/84 can only store integers up to 14 digits without loss of information, so there has to be at least a hard limit for that. And chances are finding nth palindromes that are that long would take far too long anyways. It would also be helpful for assembly programmers to know a limit; it doesn't seem right to leave us in the dark in a speed competition, encouraging us to gamble on using smaller numbers for faster math. Someone may have an advantage just because they guessed the minimal number size that still works, and someone else's efforts may completely be wasted if they used numbers slightly too small and their program ended up not passing the tests at all.

Another follow-up question, can we get a bit more information about how scoring will work? I'm especially wondering about things like how speed for varying number sizes will be scored. How will the speed of assembly programs be compared for small values, considering they may complete the computation in a fraction of a second? And if one program uses a heavy but high-end-optimized algorithm that takes, say, 0.7 seconds, 2 seconds, 8 seconds, and 36 seconds on tests while another program that uses a lighter but less high-end-optimized algorithm takes 0.2 seconds, 0.7 seconds, 5 seconds, and 114 seconds for the same tests, which would win?
I completely agree with you about the first paragraph, however for the details about notation, I'd let Critor and/or Lionel reply.
My calculator programs
TI-Planet.org co-admin.
TI-Nspire Lua programming : Tutorials  |  API Documentation

Offline Runer112

  • Moderator
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2289
  • Rating: +639/-31
    • View Profile
Re: [TI-Planet Contest] Heat up your calc with arithmetic !
« Reply #21 on: April 05, 2013, 01:21:04 pm »
I guess I have one or two more questions for now... Sorry for the slew of questions but hopefully they'll help clear things up for people besides myself as well.

  • I'm assuming that we are allowed to pre-calculate and store the values of the first few prime palindromes, like the ones with 2 or fewer digits (2, 3, 5, 7, 11), correct? Some algorithms can't really find some of these on their own and instead depend upon them being given. Storing these special cases should take less space and running time than modifying the algorithm to find them itself, and in some ways modifying the algorithm to find specific values is more or less the same thing, right?
  • Related to the question above, should we agree upon some hard rule about what values can be pre-calculated and stored? I assume this rule would either have to allow a precise set of values or an maximum amount of values.
« Last Edit: April 05, 2013, 01:22:03 pm by Runer112 »

Offline Jim Bauwens

  • Lua! Nspire! Linux!
  • Editor
  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1881
  • Rating: +206/-7
  • Linux!
    • View Profile
    • nothing...
Re: [TI-Planet Contest] Heat up your calc with arithmetic !
« Reply #22 on: April 05, 2013, 02:02:02 pm »
I guess I have one or two more questions for now... Sorry for the slew of questions but hopefully they'll help clear things up for people besides myself as well.

  • I'm assuming that we are allowed to pre-calculate and store the values of the first few prime palindromes, like the ones with 2 or fewer digits (2, 3, 5, 7, 11), correct? Some algorithms can't really find some of these on their own and instead depend upon them being given. Storing these special cases should take less space and running time than modifying the algorithm to find them itself, and in some ways modifying the algorithm to find specific values is more or less the same thing, right?
  • Related to the question above, should we agree upon some hard rule about what values can be pre-calculated and stored? I assume this rule would either have to allow a precise set of values or an maximum amount of values.

Yes, I've been wondering this too. In my current approach I have 2 and 3 hardcoded, and use 5 as a starting point. Not having them predefined would make things much more complex.

Offline critor

  • Editor
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2079
  • Rating: +439/-13
    • View Profile
    • TI-Planet
Re: [TI-Planet Contest] Heat up your calc with arithmetic !
« Reply #23 on: April 05, 2013, 03:11:30 pm »
I guess I have one or two more questions for now... Sorry for the slew of questions but hopefully they'll help clear things up for people besides myself as well.

  • I'm assuming that we are allowed to pre-calculate and store the values of the first few prime palindromes, like the ones with 2 or fewer digits (2, 3, 5, 7, 11), correct? Some algorithms can't really find some of these on their own and instead depend upon them being given. Storing these special cases should take less space and running time than modifying the algorithm to find them itself, and in some ways modifying the algorithm to find specific values is more or less the same thing, right?
  • Related to the question above, should we agree upon some hard rule about what values can be pre-calculated and stored? I assume this rule would either have to allow a precise set of values or an maximum amount of values.


There is no hard-rule, but we perfectly understand that you have to start the algorithm by intialising some variables to the 1st prime numbers.
TI-Planet co-admin.

Offline Runer112

  • Moderator
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2289
  • Rating: +639/-31
    • View Profile
Re: [TI-Planet Contest] Heat up your calc with arithmetic !
« Reply #24 on: April 05, 2013, 03:19:37 pm »
Can we pre-calculate and store answers that aren't the very first values, as long as it's not a straightforward list of all the answers? I had an idea of speeding mine up by storing, say, every 100th prime palindrome and using them as base points for calculations to reduce computation time for large inputs/outputs. If this isn't allowed, I think it should probably be made clear that except for a few starting values, your algorithm must go through all prime palindromes to get up to the target.

EDIT: Also, do we have an official ruling yet on the largest input our programs need to work on? They could certainly be different for different platforms/languages, but establishing some would be really nice.
« Last Edit: April 05, 2013, 05:02:27 pm by Runer112 »

Offline Xeda112358

  • they/them
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4659
  • Rating: +718/-6
  • Calc-u-lator, do doo doo do do do.
    • View Profile
Re: [TI-Planet Contest] Heat up your calc with arithmetic !
« Reply #25 on: April 07, 2013, 09:40:49 am »
So, I am curious, too, with what Runer is asking. For example, in TI-BASIC, although we could make a program to handle arbitrary precision, can we safely assume that we will only be using up to 14-digit numbers?
Spoiler For My Current Results:
(TI-BASIC, TI-84+SE)
Currently, my program can find the following values in the following time:
42:prgmPALPREM , 23 seconds, returns 18181
100:prgmPALPREM , 88 seconds, returns 94049
290:prgmPALPREM , 682 seconds, returns 1958591

These are big improvements over previous versions:
42 : 44→40→30→27→23
100: 280→199→135→101→88
290: 4700→2256→1375→732→682

So it has been getting a lot faster for larger numbers, but it still takes 12.2 minutes to compute the 290th term XD I have only been modifying the prime testing routine each time, but maybe if I can make the palindrome generating routine faster, I can get better times o.o
EDIT: Updated stats with version 5

Offline Lionel Debroux

  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2135
  • Rating: +290/-45
    • View Profile
    • TI-Chess Team
Re: [TI-Planet Contest] Heat up your calc with arithmetic !
« Reply #26 on: April 07, 2013, 11:21:49 am »
Given the figures you're posting, spending time on handling numbers larger than 14 digits is, indeed, unnecessary - at least for a TI-Z80 BASIC program. I don't know what the benchmarks look like for Nspire BASIC.
« Last Edit: April 07, 2013, 11:22:56 am by Lionel Debroux »
Member of the TI-Chess Team.
Co-maintainer of GCC4TI (GCC4TI online documentation), TILP and TIEmu.
Co-admin of TI-Planet.

Offline Xeda112358

  • they/them
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4659
  • Rating: +718/-6
  • Calc-u-lator, do doo doo do do do.
    • View Profile
Re: [TI-Planet Contest] Heat up your calc with arithmetic !
« Reply #27 on: April 07, 2013, 11:36:40 am »
Dapianokid said his took 11 seconds to compute the 42nd prime palindrome, but from the conversation, he may have a much more efficient algorithm for larger values. I think his was also running at 150MHz, so I am not sure.

Has anybody set any benchmarks for other languages?

Offline compu

  • LV5 Advanced (Next: 300)
  • *****
  • Posts: 275
  • Rating: +63/-3
    • View Profile
Re: [TI-Planet Contest] Heat up your calc with arithmetic !
« Reply #28 on: April 07, 2013, 03:56:44 pm »
Here are my current results for Nspire Basic, but I am not very good at things like this ;D

Offline sammyMaX

  • LV5 Advanced (Next: 300)
  • *****
  • Posts: 204
  • Rating: +9/-0
    • View Profile
Re: [TI-Planet Contest] Heat up your calc with arithmetic !
« Reply #29 on: April 07, 2013, 04:27:41 pm »
What do the rows mean? Are the upper rows the times for earlier versions of the program, and the lower rows the times for later versions?
Edit: now that I think about it, that wouldn't make sense. What do the rows mean?
« Last Edit: April 07, 2013, 04:30:00 pm by sammyMaX »

Are you wondering who Sammy is? My avatar is Sammy.