-6

I would like to use Python 2.x or 3.x to raise a 2x2 matrix that is initially

0 1
1 1

to the exponent of 1019 or less. (That is, let M = my matrix, M1019).

However, I don't want to use numpy.

(By the way, this is for a fibonacci generator )

Bhargav Rao
  • 50,140
  • 28
  • 121
  • 140
bobhob314
  • 16
  • 1
  • 9
  • Isn't this a direct HW problem. Do try something before posting! – Bhargav Rao Mar 20 '15 at 20:08
  • 3
    why don't you want to use a library like numpy for that? It's *the right thing to do*, so not doing it sounds like *the wrong thing to do*; numpy's matrixes can take many data types, including ones that fit *a lot* of precision. – Marcus Müller Mar 20 '15 at 20:11
  • Reposting this comment I made on another question b/c it applies here: Often these kinds of "how can I reinvent the wheel for no clear reason" questions don't go over well here. You don't state any clear reason for not using an existing library, but you obviously don't know how to recreate the functionality without using that library or this question wouldn't exist... you see what I mean about how that comes across? – Two-Bit Alchemist Mar 20 '15 at 20:13
  • @Two-BitAlchemist: In this case, the default numpy types won't suffice, because you just run into overruns; whilst the python int type automatically scales, the numpy types don't, so M^100 already contains negative values where it shouldn't. – Marcus Müller Mar 20 '15 at 20:16
  • @bobhob314 why would you do that for a fibonacci generator? sounds like a very complex method to do it, especially when you're not doing any acceleration. – Marcus Müller Mar 20 '15 at 20:19
  • @MarcusMüller I'm confused now. My comment was intended to explain the likely closing of this question based on the "I don't want to use the most obvious library here" and your comment. If there is some good reason `numpy` _won't work_ here (I didn't know that), shouldn't you or someone knowledgeable help the OP edit the question to clarify that's the actual problem? – Two-Bit Alchemist Mar 20 '15 at 20:23
  • @Two-BitAlchemist: I was hoping that OP would take up my comment and explain why numpy's no option and what he's been looking at. I'm currently writing an answer that involves math. – Marcus Müller Mar 20 '15 at 20:24

1 Answers1

4

Ok, the way you're asking this question really means that you stand no chance of achieving this. I'll explain; please don't be offended:

  1. Python is the wrong tool, and you're trying to exclude the helpers that would make it a little less wrong. What you're trying to do is numerical math in its purest form -- and python is a scripting language that can really only take advantage of numerical efficiency when using native libraries. One of these is numpy, but as you've probably noticed (but didn't write) that doesn't work, because your numbers get very big very fast when actually calculating Mn for larger n.
  2. even if there was a magic way to optimize the algorithm in a matter that would a allow for matrix-matrix multiplication in a single instruction and you'd only need another instruction to count and check whether you still should be multiplying to calculate Mn, your calculation would take up to 2*1019 instructions. Assuming you have a 8 CPUs that can do 4 billions of those per second, it would still take up to a little less than 20 years. What you need here is proper math. Like, really strong math. You can find a diagonal form such that M = U D U-1; U being unitary and D being a diagonal matrix. Then, using the matrix exponential e, you can get eM = U eD U. The classical exponential rules apply, so you can easily calculate eM1019. That's still ugly, but will terminate at a time that you can consider to be much safer. However, good luck implementing that without a degree in numerical mathematics.
Marcus Müller
  • 34,677
  • 4
  • 53
  • 94
  • Never mind, I got a working solution from here. http://stackoverflow.com/questions/28548457/nth-fibonacci-number-for-n-as-big-as-1019. Thanks for the downvotes though! :P – bobhob314 Mar 22 '15 at 15:38
  • @bobhob314: I really don't understand what you're saying about downvotes. Also, this clearly marks your question as duplicate. Now I have to vote for closing it. – Marcus Müller Mar 22 '15 at 16:26