13

When the first row is 1, 1/2 , 1/3 .... Here's an image to support the question. image for better description.

Does there exist a more efficient approach than the naive O(n^2) approach?

I came across this when studying Bernoulli numbers and then consequently on reaching "Akiyama–Tanigawa algorithm".

One of the ways could be simple precomputing the results and storing them in a table. Since Bernoulli numbers grow very quickly, for most practical purposes we wouldn't need Bernoulli numbers for much larger n. Consider Bernoulli(400)- its around -(10^550).

But looking at it only algorithmically, is there a better approach than the O(n^2) one?

Cœur
  • 37,241
  • 25
  • 195
  • 267
Paagalpan
  • 1,261
  • 2
  • 16
  • 25
  • I would suggest to upload your figure image to SO. – Audrius Meškauskas Apr 15 '13 at 13:23
  • Click on the picture icon while editing (on the top, right from {}). If the image appears to big for you, see also [here](http://meta.stackexchange.com/questions/165795/how-to-make-pictures-smaller) – Audrius Meškauskas Apr 15 '13 at 13:27
  • 6
    Looks as if it takes significant mathematical effort to find and prove faster methods of computation: https://en.wikipedia.org/wiki/Bernouilli_numbers#Efficient_computation_of_Bernoulli_numbers – Steve Jessop Apr 15 '13 at 13:32
  • Hmm...so you mean to say that there's no more efficient way of solving this without applying the kind of mathematics that they have applied? – Paagalpan Apr 16 '13 at 08:32
  • @NikharAgrawal: I mean to say that if there was an easy way of doing it as efficiently as those papers do it, then finding a harder way to do it that efficiently would not have been worth publishing :-) – Steve Jessop Apr 16 '13 at 08:51
  • hmm...True enough I guess. :) – Paagalpan Apr 16 '13 at 08:52
  • Assuming you're using a 1-based index. – Jacob Apr 17 '13 at 17:00
  • Voting to close as off-topic - theoretical cs or math (as the tags would suggest) – djechlin May 01 '13 at 17:45

1 Answers1

4

The first elements form the sequence of Bernoulli numbers. The numerators and denominators for the Bernoulli numbers are found using the A027641 sequence and A027642 sequence, respectively. Both of those sequences have closed-form sums on their respective pages that can be used to compute their terms.

Matthew Strawbridge
  • 19,940
  • 10
  • 72
  • 93
Brent Worden
  • 10,624
  • 7
  • 52
  • 57