8051 code find sum of first N natural numbers



Hello, guys!
Today we will see 8051 assembly program to find the sum of first N natural numbers. There are two ways to compute the sum of N natural numbers. We will go through one by one.
First method: It's simple basic code. Let's go through the algorithm.

Algorithm:
  1. Start
  2. Store the value(N) up to which sum has to be found in a register(Ra)
  3. Initialize a register(Rb) to 1
  4. Enter the loop
    • Add Rb and Accumulator register(A) and store the value in A
    • Increment Rb
    • Decrement and check whether Ra is zero
      • If Ra is zero exit the loop and move value stored in A to destination register(Rd)
      • Else, jump back and repeat the steps in loop
  5. Stop


here is an example code to find the sum of first 10 natural numbers.
Code:

    ORG OOOOh
    LJMP main
    ORG 0x40h
main:
    MOV R0,#0Ah      ; N value
    MOV R1,#01h
loop:
    ADD A,R1
    INC R1
    DJNZ R0, loop
    MOV R4,A         ; Final result is stored in register R4
end 

Second method: Using formula, It's simple and faster way to compute the sum using formula
Sum=n(n+1)/2
No need of algorithm. Example code is showed below

Code:

    ORG OOOOh
    LJMP main
    ORG 0x40h
main:
    MOV R0,#0Ah      ; N value
    MOV B,R0
    INC R0
    MOV A,R0
    MUL AB           ; n(n+1)
    MOV B,#02h
    DIV AB           ; n(n+1)/2
    MOV R4,A         ; Final result is stored in register R4
end 


Important: When to use which algorithm?
  Use the first method when your N value is small so that machine cycles reduces. And use the second method when N value is large so that you can get the result at a faster rate.
I have discussed both the methods in order to give you an idea about optimization. We will discuss more about optimization in future posts.]


Edit:

Apologies if I was not clear in explanation part. 
I have discussed the possibilities of achieving the sum of first N natural numbers. In the first method, your program size is reduced but you will have to compromise on execution time for large numbers (say numbers with 8bit size and above).  Of course, the second method is simple to understand and remember. Use the second method to save time (Remember this method takes same execution time irrespective of the value of N).


10 comments:

  1. Isn't computing n*(n+1)/2 simpler and efficient?

    ReplyDelete
  2. "When to use which algorithm?

    Use first method when your N value is small so that machine cycles reduces. And use second method when N value is large so that you can get result at faster rate."

    Define "large" and "small". I'd advise to use the second algorithm on anything larger than 5, maybe 10 (not having counted CPU cycles, I could be off a little). So, in other words, simlpy forget method 1 and always used second method.

    ReplyDelete
    Replies
    1. Hello Rob,

      As I have tested both the codes above, I observed one thing. For 3 bit number both of them takes almost similar time(around 0.00000655secs, That's hardly even a second). But as number of bits in N increases second method is best one. One thing I observed was program file size of second method is more compared to first one. May be optimization is also with memory concern, anyhow there is always trade of between speed and memory in optimization. For Embedded coder every aspect about program, file size and speed are main concerns. Panel is open for discussion and inputs.

      Delete
  3. "For 3 bit number both of them takes almost similar time(around 0.00000655secs, That's hardly even a second)"

    First, that's FAR from "hardly even a second" (it's VERY FAR from a second) and second: that's exactly what I said; "3 bit numbers" are numbers 0..7. For any other number (assuming 16 bit that's 65536-7 numbers, assuming 32 bit that's 4.2 billion and assuming 64 bit that's even WAAAY more) the second method will outperform the first method. My point was that (assuming your 3 bit numbers conclusion is correct but hell, even maybe 4 bit numbers), assuming the input is distributed evenly across the whole spectrum of numbers, the second method may cost a few more bytes but will as-good-as-always, outperform the first.

    "For Embedded coder every aspect about program, file size and speed are main concerns." And that is why I still maintain: *GENERALLY* the second method is best unless you only call the function with numbers 0..10 or something; in which case you will want the first method. But then again, a lookup table will probably be more efficient then.

    ReplyDelete
    Replies
    1. True! I totally agree with what you say. I think the content of the post should be more refined. Use of formulas makes life simple.

      Delete
  4. Thank you very much. Cleared all my doubts.
    Keep Going

    ReplyDelete
  5. After your edit it reads: "Use the first method when your N value is small". You should really DEFINE "small". 1000 is also "small" on a scale of 4 billion. But you should probably explain the O(n) vs O(1) nature of these algorithms (https://en.wikipedia.org/wiki/Big_O_notation).

    ReplyDelete
    Replies
    1. As 8051 has 128 bytes RAM and 4K ROM and up to 64K external memory. It is not feasible for high end calculations. For billions of computations we have many Microprocessor like ARM Cortex etc.8051 is just basic thing used for simple stuff.

      Delete
  6. I think you guys (codes explorer) people you should have more embedded programs in cleaner ways and start tutorial with circuits. It would be very helpful for beginners in electronics community. Hope you people will do. All the Best

    -Javed Kumar
    Embedded Engineer
    Pune, Maharashtra

    ReplyDelete
    Replies
    1. Thank you Javed for your valuable input, we will work on that in future.

      Delete

Powered by Blogger.