This <NerdAlert> is very interesting. I coded up two obvious fast versions and the slow version you mentioned (see code pasted below). The two fast versions solve the n=171 problem in 0.001 seconds on my laptop computer while the slow version solves the n=50 problem in 60.2 seconds (and the n=171 instance would take billions of years).
PS. When I was an undergrad at RPI, the word NERD was spelled KNURD because that's drunk backwards. :-)
unsigned long int fib_fast0(int n)
{
int i;
unsigned long f0=1, f1=1, f2=1;
for (i=3; i<=n; i++) {
f0 = f1+f2;
f2 = f1;
f1 = f0;
}
return f0;
}
unsigned long int fib_fast1(int n)
{
unsigned long int f1, f2;
if ( n == 0 ) return 0;
if ( n == 1 || n == 2 ) return 1;
if ( n % 2 == 1 ) {
f1 = fib_fast1((n + 1) / 2);
f2 = fib_fast1((n - 1) / 2);
return f1 * f1 + f2 * f2;
} else {
f1 = fib_fast1(n / 2 + 1);
f2 = fib_fast1(n / 2 - 1);
return f1 * f1 - f2 * f2;
}
}
unsigned long int fib_slow(int n)
{
unsigned long int f1, f2;
if ( n == 0 ) return 0;
if ( n == 1 || n == 2 ) return 1;
return fib_slow(n-1) + fib_slow(n-2);
}
------------------------------
Robert Vanderbei
Professor
Princeton University
Princeton NJ
------------------------------
Original Message:
Sent: 01-21-2018 19:28
From: Matthew Saltzman
Subject: Significance of python compared to C#
One reason C# hasn't caught on for high-performance data analysis is that the Linux/Unix implementations of C# haven't been competitive with other tools until recently. I'm not a C# programmer, but I understand from a bit of Googling that recent .NET Core releases are close to competitive on Linux with the Windows implementations.
<NerdAlert>
Sorry, I just can't resist pointing out that the C dress's code for printing the Fibonacci sequence is just about the slowest possible algorithm. It computes fibonacci(n) recursively as the sum of fibonacci(n-1) and fibonacci(n-2), which takes time exponential in n. An iterative computation would be much faster (linear in n), and a correctly implemented recursive algorithm would be faster still (O(log n)). The correct recursion with caching of intermediate results would be even faster.
The naive recursive algorithm takes 1 minute and 21 seconds to compute fibonacci(50) and 2 minutes and 15 seconds to compute fibonacci(51) on my Intel i7 (3.6GHz) laptop. The iterative method and the recursive method below compute fibonacci(93) (the largest that fits in a 64-bit unsigned integer) instantaneously. If one wanted to compute larger Fibonacci numbers with a bigint library, the difference between iterative and good recursive algorithms would become apparent
unsigned long int fibonacci(int n)
{
unsigned long int f1, f2;
if ( n == 0 ) return 0;
if ( n == 1 || n == 2 ) return 1;
if ( n % 2 == 1 ) {
f1 = fibonacci((n + 1) / 2);
f2 = fibonacci((n - 1) / 2);
return f1 * f1 + f2 * f2;
} else {
f1 = fibonacci(n / 2 + 1);
f2 = fibonacci(n / 2 - 1);
return f1 * f1 - f2 * f2;
}
}
</NerdAlert>
------------------------------
Matthew Saltzman
Clemson University
Clemson SC
Original Message:
Sent: 01-18-2018 06:45
From: Sreekanth V K
Subject: Significance of python compared to C#
Hello:
I feel that the points by @Erik Burd , especially 3-5 are important. The availability of libraries and support for solving problems is important for the research community to stick with a language. The introduction of a new language, for example the languages like Julia and all needs to compete with the community who creates this large library base of R and Python.
In addition to that Python community accepts their limitation and finds solutions for that, as the 5th one pointed out. Many python libraries use C++ code for its implementation.
------------------------------
Sreekanth V K
Research Scholar
Indian Institute of Technology Kharagpur
Kharagpur
Original Message:
Sent: 01-17-2018 06:32
From: Betty Love
Subject: Significance of python compared to C#
Those are great! Thanks!
------------------------------
Betty Love
University of Nebraska - Omaha
Omaha NE
Original Message:
Sent: 01-16-2018 12:17
From: Mary Leszczynski
Subject: Significance of python compared to C#
This is only related to this thread for the subject line.
Ladies- I just found the coolest website for dresses, and no matter your preference, you could buy a python (Python Code Fit & Flare Dress) or C (C Language Code Stripes Fit & Flare Dress) language dress! Plus a lot of other cool nerdy prints, I'm going to stock up! :)
------------------------------
Mary Leszczynski
Design & Brand Manager
INFORMS
Catonsville MD
Original Message:
Sent: 01-10-2018 21:53
From: Kiatikun Luangkesorn
Subject: Significance of python compared to C#
1. The Read, evaluate, print, loop (REPL) (an enhanced interactive prompt for those more familiar with Matlab or Mathematica) is essential for data analysis. A lot of the work is in data is trial and error, and being able to interactively try things is a big advantage that all of the main data analysis environments have.
2. To expand on the comment of Erik Burd on the active communities and libraries, a second big advantage that the main data analysis environments (Python, R, Matlab) are the quantitative and scientific libraries/packages/modules available. All are built on a foundation of linear algebra and numerical analysis libraries, and this means that other technical libraries are available using them. So R becomes probably the best environment for statistics and data analysis. Matlab if you are in electrical or chemical engineering. But Python has an additional advantage over R in that it is a well used language in a wide range of domains. So I think of Python as second to R for statistical and data analysis work, but because there are python libraries available for things such as symbolic math, optimization, simulation, and a wide range of subject specific libraries in a wide range of sciences, and that it has a wider range of facilities for managing data, working with GUI and the internet, I will often use Python because the project I'm working with is bigger than just statistics and data analysis. SciPy has a section on their website devoted to listing all of the other (than the base numerical libraries detailed at SciPy.org - SciPy.org) scientific libraries that are available in Python (Topical Software - SciPy.org), and because of this range, whenever I find myself in a situation where I need to do analytics and ____, I often find myself choosing Python.
[Background note: I used Python in my dissertation, but for teaching undergraduate and graduate analytics courses, I have settled on R as my language for teaching]
------------------------------
Louis Luangkesorn
Assistant Professor
Department of Industrial Engineering
University of Pittsburgh
Pittsburgh PA
Original Message:
Sent: 01-07-2018 15:25
From: Varalakshmi Tyaggarajan
Subject: Significance of python compared to C#
Hi,
Though Python is one of the top programming skills in the analytics world with its numerous capabilities, wondering why C# is not an equally competing programming language, especially when .Net based programming languages also support machine learning? (curious, being from .Net background). I have been surfing internet but didn't find a convincing answer. Appreciate any help here !
------------------------------
Varalakshmi T(Laks)
University of Washington-Tacoma
Tacoma WA
------------------------------