Author Topic: The Biggest Resultant Matrix  (Read 2816 times)

0 Members and 1 Guest are viewing this topic.

Offline ztrumpet

  • The Rarely Active One
  • CoT Emeritus
  • LV13 Extreme Addict (Next: 9001)
  • *
  • Posts: 5712
  • Rating: +364/-4
  • If you see this, send me a PM. Just for fun.
    • View Profile
The Biggest Resultant Matrix
« on: January 27, 2013, 02:58:55 pm »
Hello all!  It's been a while, hasn't it?

A couple of days ago, one of my professors (I'm in college now) posed the slightly rhetorical question of, "How large of a matrix can your calculators make from the multiplication of two matrices?"  I of course took it literally.  Thus, after talking to her after class and deciding to come up with the best answer I possibly could, I now have what you see below.  So sit back, and enjoy reading about just how big matrices on the TI-83/83+(SE) calcs can get:



  As discussed on Friday, I think I've figured out the biggest matrix that can be made on a TI-83/84+(SE) series of graphing calculators; it's simply limited by the amount of RAM on the calculator.  These calculators have 24389 bytes of RAM when completely empty; however, anything else, even items in archive take up RAM because of the inner workings of their operating systems.  A single matrix takes up RAM according to the following equation:

RAM = 11 + 9 * (Number of elements) bytes

  Thus, a 3x1 matrix would take up 47 bytes.  Consequently, the largest single matrix that can be made is around a 52x52 matrix (24347 bytes).

  This being said, your question was on how large the product of the multiplication of two matrices could be, which is much smaller.  Not only must all three matrices must be able to fit in RAM at the same time, but due to the inner workings of the calculator, the resulting matrix must be able to fit into RAM twice.  Assuming that we are using two vector matrices to maximize the resulting matrix, the matrices to be multiplied will be in the form 1xN and Nx1.  This allows the following equation to give the size of the largest matrix that can be multiplied on the TI-83/84+(SE) series of calculators:

RAM = (11 + 9 * N) + (11 + 9 * M) + 2*(11 + 9 * N * M) bytes

  For the ease of calculations, I'm going to assume the resulting matrix will be square, leading to this formula:

RAM = 2*(11 + 9 * N) + 2*(11 + 9 * N * N) bytes
RAM = 18N^2 + 18N + 44 bytes

  When solved, this gives a maximum matrix size of 36x36 (totaling to 24020 bytes).  However, this was assuming that the two matrices being multiplied were both vectors.  If the two matrices are both square, then the size drops dramatically:

RAM = 4*(11 + 9 * N^2) bytes

  Here, the largest resultant matrix is 25x25 (totaling to 22544 bytes).  It's worth noting that by the equations given it seems possible to multiply two 26x26 matrices.  However, though by my equations they total to 24380 bytes (9 shy of the RAM limit), there are actually a few more things that go into RAM - such as typing the equation to multiply the two matrices on the homescreen of the calculator - that makes the 26x26s slightly too large to be multiplied.

  Thus, on an empty TI-83/83+(SE) calculator it's possible to multiply matrices as large as 25x25, but the result can be as large as 36x36 if the two initial matrices are vectors.

Offline DJ Omnimaga

  • Former TI programmer
  • CoT Emeritus
  • LV15 Omnimagician (Next: --)
  • *
  • Posts: 55872
  • Rating: +3151/-232
  • CodeWalrus founder & retired Omnimaga founder
    • View Profile
    • DJ Omnimaga Music
Re: The Biggest Resultant Matrix
« Reply #1 on: January 27, 2013, 03:37:21 pm »
Nice to see you again. Interesting stuff Ztrumpet. I do remember the annoyances of matrices taking twice the amount of RAM on calcs and I think I had this happen with strings too. The Ans variable, while being useful, can be quite annoying too sometimes. This is why for games with maps, I heard that some people prefered to update each element one by one, so that Ans only takes the amount of RAM a variable value would require.

Also the TI-84 Plus C Silver Edition has between 21772 and 21872 bytes of RAM I think, so this will make matrices multiplying even harder.

Offline blue_bear_94

  • LV8 Addict (Next: 1000)
  • ********
  • Posts: 801
  • Rating: +25/-35
  • Touhou Enthusiast / Former Troll / 68k Programmer
    • View Profile
Re: The Biggest Resultant Matrix
« Reply #2 on: January 27, 2013, 03:45:29 pm »
I wonder how big a resultant matrix could be on the TI-89...
Due to dissatisfaction, I will be inactive on Omnimaga until further notice. (?? THP hasn't been much success and there's also the CE. I might possibly be here for a while.)
If you want to implore me to come back, or otherwise contact me, I can be found on GitHub (bluebear94), Twitter (@melranosF_), Reddit (/u/Fluffy8x), or e-mail (if you know my address). As a last resort, send me a PM on Cemetech (bluebear94) or join Touhou Prono (don't be fooled by the name). I've also enabled notifications for PMs on Omnimaga, but I don't advise using that since I might be banned.
Elvyna (Sunrise) 4 5%
TI-84+SE User (2.30 2.55 MP 2.43)
TI-89 Titanium User (3.10)
Casio Prizm User? (1.02)
Bag  東方ぷろの

Offline Juju

  • Incredibly sexy mare
  • Coder Of Tomorrow
  • LV13 Extreme Addict (Next: 9001)
  • *************
  • Posts: 5730
  • Rating: +500/-19
  • Weird programmer
    • View Profile
    • juju2143's shed
Re: The Biggest Resultant Matrix
« Reply #3 on: January 27, 2013, 03:52:04 pm »
I guess you're right. Say you have 3 matrix size variables, m, n and p, you can only multiply a mxp with a pxn matrix, which would result in a mxn matrix. I guess you can easily calculate something out of this, I assume you'll have to fit all three matrices in RAM.

So (11+9m+9p)+(11+9p+9n)+(11+9m+9n)<24389 where m,n,p are integers >1. It isn't easy because there's 3 variables...

For the homescreen it's kinda simple, you would only do [A]*[B]->[C] (which is 8 bytes if the [A] tokens are 2 bytes), so 24389-8.

To simplify, maximize 33+18m+18n+18p < 24381.
« Last Edit: January 27, 2013, 04:13:04 pm by Juju »

Remember the day the walrus started to fly...

I finally cleared my sig after 4 years you're happy now?
THEGAME
This signature is ridiculously large you've been warned.

The cute mare that used to be in my avatar is Yuki Kagayaki, you can follow her on Facebook and Tumblr.

Offline Levak

  • LV9 Veteran (Next: 1337)
  • *********
  • Posts: 1002
  • Rating: +208/-39
    • View Profile
    • My website
Re: The Biggest Resultant Matrix
« Reply #4 on: January 27, 2013, 04:06:34 pm »
Now do it for the TI-Nspire CX.

Ready, Steady, Go.
I do not get mad at people, I just want them to learn the way I learnt.
My website - TI-Planet - iNspired-Lua

Offline blue_bear_94

  • LV8 Addict (Next: 1000)
  • ********
  • Posts: 801
  • Rating: +25/-35
  • Touhou Enthusiast / Former Troll / 68k Programmer
    • View Profile
Re: The Biggest Resultant Matrix
« Reply #5 on: January 27, 2013, 07:39:28 pm »
I guess you're right. Say you have 3 matrix size variables, m, n and p, you can only multiply a mxp with a pxn matrix, which would result in a mxn matrix. I guess you can easily calculate something out of this, I assume you'll have to fit all three matrices in RAM.

So (11+9m+9p)+(11+9p+9n)+(11+9m+9n)<24389 where m,n,p are integers >1. It isn't easy because there's 3 variables...

For the homescreen it's kinda simple, you would only do [A]*[B]->[C] (which is 8 bytes if the [A] tokens are 2 bytes), so 24389-8.

To simplify, maximize 33+18m+18n+18p < 24381.
You don't need to put the "*", and you also need to think about Ans.
Due to dissatisfaction, I will be inactive on Omnimaga until further notice. (?? THP hasn't been much success and there's also the CE. I might possibly be here for a while.)
If you want to implore me to come back, or otherwise contact me, I can be found on GitHub (bluebear94), Twitter (@melranosF_), Reddit (/u/Fluffy8x), or e-mail (if you know my address). As a last resort, send me a PM on Cemetech (bluebear94) or join Touhou Prono (don't be fooled by the name). I've also enabled notifications for PMs on Omnimaga, but I don't advise using that since I might be banned.
Elvyna (Sunrise) 4 5%
TI-84+SE User (2.30 2.55 MP 2.43)
TI-89 Titanium User (3.10)
Casio Prizm User? (1.02)
Bag  東方ぷろの

Offline fb39ca4

  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1749
  • Rating: +60/-3
    • View Profile
Re: The Biggest Resultant Matrix
« Reply #6 on: January 27, 2013, 09:26:28 pm »
Now do it for the TI-Nspire CX.

Ready, Steady, Go.
Do those have 128MB of RAM, or just 128MB of flash and 32MB RAM?

Offline epic7

  • Chopin!
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2200
  • Rating: +135/-8
  • I like robots
    • View Profile
Re: The Biggest Resultant Matrix
« Reply #7 on: January 27, 2013, 09:27:57 pm »
I think the CX has 64MB of RAM

Offline Juju

  • Incredibly sexy mare
  • Coder Of Tomorrow
  • LV13 Extreme Addict (Next: 9001)
  • *************
  • Posts: 5730
  • Rating: +500/-19
  • Weird programmer
    • View Profile
    • juju2143's shed
Re: The Biggest Resultant Matrix
« Reply #8 on: January 27, 2013, 09:39:37 pm »
I guess you're right. Say you have 3 matrix size variables, m, n and p, you can only multiply a mxp with a pxn matrix, which would result in a mxn matrix. I guess you can easily calculate something out of this, I assume you'll have to fit all three matrices in RAM.

So (11+9m+9p)+(11+9p+9n)+(11+9m+9n)<24389 where m,n,p are integers >1. It isn't easy because there's 3 variables...

For the homescreen it's kinda simple, you would only do [A]*[B]->[C] (which is 8 bytes if the [A] tokens are 2 bytes), so 24389-8.

To simplify, maximize 33+18m+18n+18p < 24381.
You don't need to put the "*", and you also need to think about Ans.
You are right. [C] and Ans would be redundant, so you can do [A][B] and you save 4 bytes plus the number of bytes the resulting matrix takes up in RAM.

33+18m+18n+18p <= 24385
« Last Edit: January 27, 2013, 09:40:21 pm by Juju »

Remember the day the walrus started to fly...

I finally cleared my sig after 4 years you're happy now?
THEGAME
This signature is ridiculously large you've been warned.

The cute mare that used to be in my avatar is Yuki Kagayaki, you can follow her on Facebook and Tumblr.