Question

In: Computer Science

Count the number of flops (floating point operations) in the following pseudocode: for i=1:n   for j=1:i    ...

Count the number of flops (floating point operations) in the following pseudocode:

for i=1:n  

for j=1:i    

for k=j:n      

y=y+aijxij    

end  

end

end

Solutions

Expert Solution

This question isn't really a matlab question. You can also apply brute force(checking every condition and add it) way of working it out.

Question.

for i=1:n  

for j=1:i    

for k=j:n      

y=y+aij * xij    

end  

end

end

1: The inner equation has two flops, so the k (j -> n) loop has 2(n-j+1) flops.

2: Now Move to j loop (1 -> i ):

summation of 2(n-j+1) i times in j loop ( here q = 2(n-j+1) ) 

 it helps to know the sum of q from 1 -> i is i(i+1)/2 and q^2 from 1 to i is i(i+1)(2i+1)/6.

The j loop is of 2(n-j+1) for j from 1 -> i, so it has 2i(n+1)-i(i+1)=2i(n+1/2)-i^2 flops.

3: The overall, or i, loop is a sum of 2i(n+1/2)-i^2, giving n(n+1)(n+1/2) - n(n+1)(2n+1)/6 = n(n+1)(2n+1)/3.

You can see that this is the same as the sum from 1 to n of 2i^2.

A way to check this, e.g. in matlab, is to set some n, and put f=0 at the start and replace the inner equation with f=f+2;, then the result will be f=n(n+1)(2n+1)/3.



Total flipflop : f=n(n+1)(2n+1)/3.

Related Solutions

Convert the following floating-point number (stored using IEEE floating-point standard 754) to a binary number in...
Convert the following floating-point number (stored using IEEE floating-point standard 754) to a binary number in non-standard form. 0100_0001_1110_0010_1000_0000_0000_0000
Write a Program(code) in Python that performs a large number of floating-point operations and an equal...
Write a Program(code) in Python that performs a large number of floating-point operations and an equal number of integer operations and compares the time required. Please attach an output.
Assume that you have a 12-bit floating point number system, similar to the IEEE floating point...
Assume that you have a 12-bit floating point number system, similar to the IEEE floating point standard, with the format shown below and a bias of 7. The value of a floating point number in this system is represented as    FP = (-1)^S X 1.F X 2^(E-bias) for the floating point numbers A = 8.75 and B = -5.375. The binary representation of A is given as A = 0101 0000 1100 Show the hexidecimal representation of B.
Using the simple model for representing binary floating point numbers A floating-point number is 14 bits...
Using the simple model for representing binary floating point numbers A floating-point number is 14 bits in length. The exponent field is 5 bits. The significand field is 8 bits. The bias is 15 Represent -32.5010 in the simple model.
Convert the following number into 32bit IEEE 754 floating point representation. 0.000101
Convert the following number into 32bit IEEE 754 floating point representation. 0.000101
4. Given Pseudocode: Algorithm3(n): y = 0 for i = 1 to n do y =...
4. Given Pseudocode: Algorithm3(n): y = 0 for i = 1 to n do y = 1 while y < i2 do y=2y return y a. What's the output of Algorithm3(n) as a function of n? b. What's the running time of Algorithm3(n) as a function of n? Represent this as a summation. c. Prove the running time to be O(n log n).
int f2 (int n) j = 0; while (j <n) {for (int i = 0; i...
int f2 (int n) j = 0; while (j <n) {for (int i = 0; i <n; ++ i) {cout << "j =" + j; j = j + 5; }}
Concern the following 16-bit floating point representation: The first bit is the sign of the number...
Concern the following 16-bit floating point representation: The first bit is the sign of the number (0 = +, 1 = -), the next nine bits are the mantissa, the next bit is the sign of the exponent, and the last five bits are the magnitude of the exponent. All numbers are normalized, i.e. the first bit of the mantissa is one, except for zero which is all zeros. 1. What's the smallest difference between two consecutive or adjacent numbers?...
Let Ti, i=1, … ,n be a set of dates, on which payments of the floating...
Let Ti, i=1, … ,n be a set of dates, on which payments of the floating leg of an interest rate swap occur. The payoff of the floating leg of the swap at time Ti is Fi + s where Fi is the reference rate of the floating leg and s is a constant spread. For simplicity, let’s assume that the floating and fixed payments happen on the same dates. Also, ri is the risk-free rate on the same tenor....
Consider the following 32-bit floating point representation based on the IEEE floating point standard: There is...
Consider the following 32-bit floating point representation based on the IEEE floating point standard: There is a sign bit in the most significant bit. The next eight bits are the exponent, and the exponent bias is 28-1-1 = 127. The last 23 bits are the fraction bits. The representation encodes number of the form V = (-1)S x M x 2E, where S is the sign, M is the significand, and E is the biased exponent. The rules for the...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT