# 2020q3 Homework5 (quiz5) contributed by < [stonelin](https://github.com/StoneLin0708) > ###### tags: sysprog2020 ## Test 1 c #include <stdio.h> #include <stdlib.h> double divop(double orig, int slots) { if (slots == 1 || orig == 0) return orig; int od = slots & 1; double result = divop(orig / 2, od ? (slots + 1) >> 1 : slots >> 1); if (od) result += divop(result, slots); return result; }  A 32 bit floating point number can be represented as [$sign,exp_0\ ...\ exp_7,fraction_0\ ...\ fraction_{22}$] Float to integer division can be recursive solved by **given** $F\in float_{Nbit}\\ I\in\mathbf{Z}$ $I_{even}=2(I_{even}>>1)\\ I_{odd}=2(I_{odd}>>1)+1$ **Therefor** **If I is even** $\dfrac{F}{I_{even}} =\dfrac{F/2}{I_{even}>>1}$ **If I is odd** $\dfrac{F}{I_{odd}} =\dfrac{F}{2(I_{odd}>>1)+1}= \dfrac{F/2}{(I_{odd}>>1)+1/2} =\dfrac{F/2}{((I_{odd}+1)>>1)-1/2}\\ =\dfrac{F/2}{((I_{odd}+1)>>1)}\dfrac{((I_{odd}+1)>>1)}{((I_{odd}+1)>>1)-1/2}\\ =>((I_{odd}+1)>>1)=k\\ =\dfrac{F/2}{k}\dfrac{k}{k-1/2} =\dfrac{F/2}{k}(1+\dfrac{1/2}{k-1/2})\\ =result(1+\dfrac{1/2}{k-1/2}) =result+\dfrac{result}{2k-1}\\ =result+\dfrac{result}{2((I_{odd}+1)>>1)-1} =result+\dfrac{result}{I_{odd}+1-1} =result+\dfrac{result}{I_{odd}} .$ ### tail recursion * It might conditional generate another resursion between result and return, therefor there is no tail recursion exists. ### reduce fpu usage by integer floating point divide 2 * it run a lot slower than just using floating point division (about 150x) * c++ use less instruction in my case * resursion use 50 x86 instruction and fpu use 2 <iframe width="1000px" height="800px" src="https://godbolt.org/e#z:OYLghAFBqd5TKALEBjA9gEwKYFFMCWALugE4A0BIEAZugHZEDKqAhgDbYgCMALOQCse5dq3qhUAUgBMAIRmzyAZ2ydURAg2rZ6mAMLp2AVwC29ENPI7MAGQL1sAOVMAjbKRC8AnOQAO6JWJNegNjM2F/QI0GOwdnEzcPXgA2ZVVsdWCmIlZSIlDTc0sVNWj6bNyiWKdXd08fJRy8gvDuZSaq%2BxqEupSASmV0I1JULgByGQBme1RjHABqSUm9VEbCRiXcSQAGAEEpmbnsReXVokJ0TZ39vft2LvnWIxJ5kgJadnRWInmaPskAOzyPbzUHzUjYIjDejzABUEPsRHcvghRAA%2BmxGks9EZEZNpGiiLDNhAZMk/ktgfsAQARa7XO4PJ4vEg0CC4xj4wm/f5A65g8GQ6FwhGMZGojGsLHLGifb7Eya4UnScn/SZUwF0vbXJEmXyiJHYogAT18OlYJmOABUrnsrb9CAA3aQQK1qjV7XX677YbG23aMhzzDlELk/GhO6TYkNhkkxgk/Ai8qkCjD0RrBvEJ%2BbYAAevhONPmEAIixV822uYBADEABzbBsNtVbRXSSaU/lgghsvO%2BJZ0yY07h9QVQ0gw7YdkFg1HCktl5IV3P1mvVtfVkeAvTFqC9gC0w79yzbm/LlZr9cb23d9Np9M92D1Bt9y39geOsq%2B4cj2M/3xJf7hsmnagrO46vOgbIRgQzoQG8tB9IhU7UlqNy7F6z5Gqa5qWvM1b%2BtW8xOugvgQIRZAEMA5DzIi8xKJ8RBKDe2oPk%2BPpHlseyAURMEkb%2BcpEABAnzBRVE0YwdEMUxix8tOoLdsW9HoIxhb9vM3AyXoW7FqJqmDhWSFyQKo7CqJyECgpEBKSpZLqcBRkCsy6CCkohY8Y6JG0JGECiQMilSWWsh2ScLa4HZ5nGaBQrgRCrkKO5nmxdR1lMRFoKaqoKiAimkUmeBxGkdBsG%2BclAVXIq4XqiBMmoZq95odxrBudwAB00gAKzIWmjS9qQ4k/C4zVRlVLEBhJJisPYED2bsAoooibIyFGHU0JI7V6PQS3kKwAD0LjMbNYLzYwi3SMt7Wretm1neQBUQKw5D7QdmpjAM7AgGM7VjOQ5hjNs33oB9WlyPFShDCMxxTNw31EB9/2IeQADWICTACLWTLW3DcJjKrtV4%2BKo6k71jLw30mCA7XbD9cMAx931KCAVOw39r3kHAsAoBgeoEJwFBUBAXO%2BDzdSzGIwBYw25A0DzSKkAzEAuDTj32LkxofdD5Bc5ajAAPL0Owass7dj5i5wSuEBCmSOtgDNG3mGTPOMGuIqoSv3C4pCqwYODqzDpAEOTYzQwMdCMCwHBcHwgjCKI4hoAoCgiAQLgM5AAwkWUtt7jrkz0%2BkmRaBA1gtOYbTWNU8SJBEARBAwJfV1EwQV7UHhtCUGRlBUzSGIUwjtwX5QdM3PSt%2B0lT123Q9dJXdTDoMwyjDwb0fV91NG4DYzLske7JLw8yi%2BI6mtdsLXbMW%2BDEGQZaTG08wGNzvPX8Od8J3IMM0wjSDYKwOAeNNSP1HRtjbY0gvDbGSO1bghMAQiA%2BqTNe/1yAb3pozcgzN4Zs0QBAFA9tUDPDIJQaguRgBKAAApiFUEwJA6AADuv0NaCx5t8YI5CHDsCobQ36iDGG8zQLHcW3BJY8PcDrZ4HC6FK1wbsUgJC6ZWFzBkbI6w5Gh2YGwM2UchBtH4fHEGcgk4p3gOnXwmcPrZ1zvPCGfdzj2FYZQ6hEig6s2JqvLhtNN61m3rvfe/Cj6n1PvMXACi8EkD6hAC%2BoSn4jmBvIN%2BaCP4DC/j/Oo/9kZQPRg2AEtYvDJGSNk0BXhIGwJJt9NxSC5EMyZgk4p0gyYUypmU5B8SWYDHZggeA2C0BYDwIQUJhDaAMDURHHg/AhCWB0WiSZqA0ilGCNoXQ9dLDl2ni3FGbRIi1xCD3cIlgNllGHlXG%2BMyO5ZA6Is45A8u6dDiKso5jRx7bKKGPPIBy6g3wGGDBe4wDj0FmEYBY2I1iIhakgf0Py/kAuWEC9AIKwVcWEkVF03EKSyUOqCeM3JSxqVhOyLMhJYT/BVKtEaaL94MAzBin4vY3LzlsueOsV5rzlVwG2NKNEez5n7P2Z%2BYEJxsspS5GlWKzzLm2Kudcm4ATbigEXfMB41RaWPJMU8i56WXkbAdAUvK4QfC/ASsksVkJ1VGtcbid1uKiWorRFKkqcryRoP5ZScVBxqQ0lubSPl/bAD0kWa8/wHIzmijCMyJKLIOqsmVcsh5UW5V%2BMJWKblzXeRKo6mychgrMsqna4y2qE3xTuklSSTrNVggyuwLKMbcraqTTBF0KaUohU2Fm6qxqUL1VNcJJqrq2qdRJbRQarrhoejGj8CaU0ZpzX9idZU51LobS2rtfabLjpEFOrOta86bp3Qek9I1tJnEr1KUrDe25PkQ2vrU5p8NEnf1/tQAYyNUbow6pMVG0huAAl3tIXgkx2rFPgeTSmCD3EoKqS0zBHTOboAfu4fpwiPCoAPgIyW0t2Cy3lorI2LgVakENgw6D2siB6wNubE24gzZGwtic62ttEG4Mdr7SgYpiaIPdp7XD3snZ%2BwDr7EOgzw4aNGRYEQYsQCTIxAY1O/8M7BCzjnPOszC7F0ecIZZNyR4N02RPPwNd9krI023fOnczkqcM4pwelRXmj3ud3MIpdnnXO6FXOeZ7F7SGXp9I968Ppbx3nvJDfiT5n3Cb0q%2BUxLB32g0LR%2B4XonvxaTe5Jf8H2AN4NjLGtZpAAi8ACSYOWIH/q84gpplSr2szaZ0%2BjfT%2BbELIRQ9hDj6HfR4cwhgdiGucKVvBtASGJZU3g6I5gjXJHBOkbIsY31cFKPsCo/j6jI5CfGaJ8T0z3ZSeMaYsY5j6bgzc%2B0dY7XxFNY86449PnPF%2BZ8WLQLASgkO0iSFy%2BfVYt33i9e8gSS72pJ4JMHtEDeC8EpiqD92WiZwKKyB5QqD0GvQ85ewDDSzsTbKwjNJktiYWMaXImHCNrZyzmbwIAA%3D"></iframe> ## Test 3 c int consecutiveNumbersSum(int N) { if (N < 1) return 0; int ret = 1; int x = N; for (int i = 2; i < x; i++) { x += 1-i; if (x % i == 0) ret++; } return ret; }  $N=\Sigma_{i=0}^{h-1}x+i\\ N=(x+x+h-1)h/2\\ N=(2x+h-1)h/2\\ N=xh+(h-1)h/2\\ N-h(h-1)/2=xh$ Therefor the answer is number of integer soultion of $\dfrac{N-h(h-1)/2}{h}\forall{h\in{Z^+}}$ loop through h $x=N-h(h-1)/2$ $x_{h=0}=N$ $x_{h=1}=N$ $x_{h=2}=N-1$ $x_{h=3}=N-3=N-1-2$ $x_{h=4}=N-6=N-1-2-3$ $x_{h=i}=N-1-2-3\ ...\ -(i-1)$ $x_{h=i}=N-1-2-3\ ...\ +(1-i)$