# 2020q3 Homework5 (quiz5)
contributed by < [stonelin](https://github.com/StoneLin0708) >

###### tags: `sysprog2020`

## Test 1

#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

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)$