8
\$\begingroup\$

There is a question on the site that asks to implement division without using division.

In my case, I am asking you to do the same, but only using addition.

What this means is basically: addition is the only operator or function allowed that operates on numbers and returns other numbers (i.e. no subtraction, multiplication, exponentiation, bitwise inversion, etc.). Stuff like if statements, assignment and comparison operators, and for loops are still allowed, provided that within those, you still only use addition.

Your task is to build a function divide(a, b) that takes two positive integers a and b and returns the result of a being divided by b and rounded toward zero, but using addition and no other arithmetical operators, and no other data constructs besides numbers.

The code that wins will be the one that requires the fewest addition operations to be performed over the set of inputs where a varies from 1 to 200 and b varies from 1 to a.

To keep track of this, you can build an alternate version of your code that replaces every instance of a + b with add(a, b) and program add to increment a global add_used variable as well as returning the sum of the two numbers.

\$\endgroup\$
  • \$\begingroup\$ I'm probably not going to accept any answer, just because there were too many loopholes in this question for it to be meaningful. \$\endgroup\$ – Joe Z. Sep 15 '13 at 16:55
  • 1
    \$\begingroup\$ eBusiness answered the challenge well, imho. A lookup table solves the challenge without any additions. Yes, it's a bit humorous, but what the heck? I also like Johannes Kuhn's approach. You moved the goalposts to disqualify his entry. That, to me, was unfair. \$\endgroup\$ – DavidC Sep 15 '13 at 17:25
  • \$\begingroup\$ I agree that he answered the challenge well, and I upvoted his answer for that. But it feels wrong to accept an answer just because the goalposts were incorrectly placed in the first place. \$\endgroup\$ – Joe Z. Sep 15 '13 at 19:29
  • \$\begingroup\$ You managed it to disqualify 2 of my answers. Ok, the first one used the division function (which was not an operator at that time), so better leave that deleted. \$\endgroup\$ – Johannes Kuhn Sep 17 '13 at 7:29

17 Answers 17

17
\$\begingroup\$

Writing rules is hard, these rules in particular contain incentive to avoid additions at all costs.

Is there a prize for the most ridiculous answer?

JavaScript - 0 additions

Now with fallback method that does a hulking solution for larger a's and b's, and a slightly more compact structure in order not to bust the character limit. (Pfff, 30000 characters. What is this? Twitter?) Still no additions in the measured scope.

function divide(a,b){
    if(a<b){
        return 0
    }
    if(b==1){
        return a
    }
    if(b==2){
        if(a<4){return 1}
        if(a<6){return 2}
        if(a<8){return 3}
        if(a<10){return 4}
        if(a<12){return 5}
        if(a<14){return 6}
        if(a<16){return 7}
        if(a<18){return 8}
        if(a<20){return 9}
        if(a<22){return 10}
        if(a<24){return 11}
        if(a<26){return 12}
        if(a<28){return 13}
        if(a<30){return 14}
        if(a<32){return 15}
        if(a<34){return 16}
        if(a<36){return 17}
        if(a<38){return 18}
        if(a<40){return 19}
        if(a<42){return 20}
        if(a<44){return 21}
        if(a<46){return 22}
        if(a<48){return 23}
        if(a<50){return 24}
        if(a<52){return 25}
        if(a<54){return 26}
        if(a<56){return 27}
        if(a<58){return 28}
        if(a<60){return 29}
        if(a<62){return 30}
        if(a<64){return 31}
        if(a<66){return 32}
        if(a<68){return 33}
        if(a<70){return 34}
        if(a<72){return 35}
        if(a<74){return 36}
        if(a<76){return 37}
        if(a<78){return 38}
        if(a<80){return 39}
        if(a<82){return 40}
        if(a<84){return 41}
        if(a<86){return 42}
        if(a<88){return 43}
        if(a<90){return 44}
        if(a<92){return 45}
        if(a<94){return 46}
        if(a<96){return 47}
        if(a<98){return 48}
        if(a<100){return 49}
        if(a<102){return 50}
        if(a<104){return 51}
        if(a<106){return 52}
        if(a<108){return 53}
        if(a<110){return 54}
        if(a<112){return 55}
        if(a<114){return 56}
        if(a<116){return 57}
        if(a<118){return 58}
        if(a<120){return 59}
        if(a<122){return 60}
        if(a<124){return 61}
        if(a<126){return 62}
        if(a<128){return 63}
        if(a<130){return 64}
        if(a<132){return 65}
        if(a<134){return 66}
        if(a<136){return 67}
        if(a<138){return 68}
        if(a<140){return 69}
        if(a<142){return 70}
        if(a<144){return 71}
        if(a<146){return 72}
        if(a<148){return 73}
        if(a<150){return 74}
        if(a<152){return 75}
        if(a<154){return 76}
        if(a<156){return 77}
        if(a<158){return 78}
        if(a<160){return 79}
        if(a<162){return 80}
        if(a<164){return 81}
        if(a<166){return 82}
        if(a<168){return 83}
        if(a<170){return 84}
        if(a<172){return 85}
        if(a<174){return 86}
        if(a<176){return 87}
        if(a<178){return 88}
        if(a<180){return 89}
        if(a<182){return 90}
        if(a<184){return 91}
        if(a<186){return 92}
        if(a<188){return 93}
        if(a<190){return 94}
        if(a<192){return 95}
        if(a<194){return 96}
        if(a<196){return 97}
        if(a<198){return 98}
        if(a<200){return 99}
        if(a<202){return 100}
    }
    if(b==3){
        if(a<6){return 1}
        if(a<9){return 2}
        if(a<12){return 3}
        if(a<15){return 4}
        if(a<18){return 5}
        if(a<21){return 6}
        if(a<24){return 7}
        if(a<27){return 8}
        if(a<30){return 9}
        if(a<33){return 10}
        if(a<36){return 11}
        if(a<39){return 12}
        if(a<42){return 13}
        if(a<45){return 14}
        if(a<48){return 15}
        if(a<51){return 16}
        if(a<54){return 17}
        if(a<57){return 18}
        if(a<60){return 19}
        if(a<63){return 20}
        if(a<66){return 21}
        if(a<69){return 22}
        if(a<72){return 23}
        if(a<75){return 24}
        if(a<78){return 25}
        if(a<81){return 26}
        if(a<84){return 27}
        if(a<87){return 28}
        if(a<90){return 29}
        if(a<93){return 30}
        if(a<96){return 31}
        if(a<99){return 32}
        if(a<102){return 33}
        if(a<105){return 34}
        if(a<108){return 35}
        if(a<111){return 36}
        if(a<114){return 37}
        if(a<117){return 38}
        if(a<120){return 39}
        if(a<123){return 40}
        if(a<126){return 41}
        if(a<129){return 42}
        if(a<132){return 43}
        if(a<135){return 44}
        if(a<138){return 45}
        if(a<141){return 46}
        if(a<144){return 47}
        if(a<147){return 48}
        if(a<150){return 49}
        if(a<153){return 50}
        if(a<156){return 51}
        if(a<159){return 52}
        if(a<162){return 53}
        if(a<165){return 54}
        if(a<168){return 55}
        if(a<171){return 56}
        if(a<174){return 57}
        if(a<177){return 58}
        if(a<180){return 59}
        if(a<183){return 60}
        if(a<186){return 61}
        if(a<189){return 62}
        if(a<192){return 63}
        if(a<195){return 64}
        if(a<198){return 65}
        if(a<201){return 66}
    }
    if(b==4){
        if(a<8){return 1}
        if(a<12){return 2}
        if(a<16){return 3}
        if(a<20){return 4}
        if(a<24){return 5}
        if(a<28){return 6}
        if(a<32){return 7}
        if(a<36){return 8}
        if(a<40){return 9}
        if(a<44){return 10}
        if(a<48){return 11}
        if(a<52){return 12}
        if(a<56){return 13}
        if(a<60){return 14}
        if(a<64){return 15}
        if(a<68){return 16}
        if(a<72){return 17}
        if(a<76){return 18}
        if(a<80){return 19}
        if(a<84){return 20}
        if(a<88){return 21}
        if(a<92){return 22}
        if(a<96){return 23}
        if(a<100){return 24}
        if(a<104){return 25}
        if(a<108){return 26}
        if(a<112){return 27}
        if(a<116){return 28}
        if(a<120){return 29}
        if(a<124){return 30}
        if(a<128){return 31}
        if(a<132){return 32}
        if(a<136){return 33}
        if(a<140){return 34}
        if(a<144){return 35}
        if(a<148){return 36}
        if(a<152){return 37}
        if(a<156){return 38}
        if(a<160){return 39}
        if(a<164){return 40}
        if(a<168){return 41}
        if(a<172){return 42}
        if(a<176){return 43}
        if(a<180){return 44}
        if(a<184){return 45}
        if(a<188){return 46}
        if(a<192){return 47}
        if(a<196){return 48}
        if(a<200){return 49}
        if(a<204){return 50}
    }
    if(b==5){
        if(a<10){return 1}
        if(a<15){return 2}
        if(a<20){return 3}
        if(a<25){return 4}
        if(a<30){return 5}
        if(a<35){return 6}
        if(a<40){return 7}
        if(a<45){return 8}
        if(a<50){return 9}
        if(a<55){return 10}
        if(a<60){return 11}
        if(a<65){return 12}
        if(a<70){return 13}
        if(a<75){return 14}
        if(a<80){return 15}
        if(a<85){return 16}
        if(a<90){return 17}
        if(a<95){return 18}
        if(a<100){return 19}
        if(a<105){return 20}
        if(a<110){return 21}
        if(a<115){return 22}
        if(a<120){return 23}
        if(a<125){return 24}
        if(a<130){return 25}
        if(a<135){return 26}
        if(a<140){return 27}
        if(a<145){return 28}
        if(a<150){return 29}
        if(a<155){return 30}
        if(a<160){return 31}
        if(a<165){return 32}
        if(a<170){return 33}
        if(a<175){return 34}
        if(a<180){return 35}
        if(a<185){return 36}
        if(a<190){return 37}
        if(a<195){return 38}
        if(a<200){return 39}
        if(a<205){return 40}
    }
    if(b==6){
        if(a<12){return 1}
        if(a<18){return 2}
        if(a<24){return 3}
        if(a<30){return 4}
        if(a<36){return 5}
        if(a<42){return 6}
        if(a<48){return 7}
        if(a<54){return 8}
        if(a<60){return 9}
        if(a<66){return 10}
        if(a<72){return 11}
        if(a<78){return 12}
        if(a<84){return 13}
        if(a<90){return 14}
        if(a<96){return 15}
        if(a<102){return 16}
        if(a<108){return 17}
        if(a<114){return 18}
        if(a<120){return 19}
        if(a<126){return 20}
        if(a<132){return 21}
        if(a<138){return 22}
        if(a<144){return 23}
        if(a<150){return 24}
        if(a<156){return 25}
        if(a<162){return 26}
        if(a<168){return 27}
        if(a<174){return 28}
        if(a<180){return 29}
        if(a<186){return 30}
        if(a<192){return 31}
        if(a<198){return 32}
        if(a<204){return 33}
    }
    if(b==7){
        if(a<14){return 1}
        if(a<21){return 2}
        if(a<28){return 3}
        if(a<35){return 4}
        if(a<42){return 5}
        if(a<49){return 6}
        if(a<56){return 7}
        if(a<63){return 8}
        if(a<70){return 9}
        if(a<77){return 10}
        if(a<84){return 11}
        if(a<91){return 12}
        if(a<98){return 13}
        if(a<105){return 14}
        if(a<112){return 15}
        if(a<119){return 16}
        if(a<126){return 17}
        if(a<133){return 18}
        if(a<140){return 19}
        if(a<147){return 20}
        if(a<154){return 21}
        if(a<161){return 22}
        if(a<168){return 23}
        if(a<175){return 24}
        if(a<182){return 25}
        if(a<189){return 26}
        if(a<196){return 27}
        if(a<203){return 28}
    }
    if(b==8){
        if(a<16){return 1}
        if(a<24){return 2}
        if(a<32){return 3}
        if(a<40){return 4}
        if(a<48){return 5}
        if(a<56){return 6}
        if(a<64){return 7}
        if(a<72){return 8}
        if(a<80){return 9}
        if(a<88){return 10}
        if(a<96){return 11}
        if(a<104){return 12}
        if(a<112){return 13}
        if(a<120){return 14}
        if(a<128){return 15}
        if(a<136){return 16}
        if(a<144){return 17}
        if(a<152){return 18}
        if(a<160){return 19}
        if(a<168){return 20}
        if(a<176){return 21}
        if(a<184){return 22}
        if(a<192){return 23}
        if(a<200){return 24}
        if(a<208){return 25}
    }
    if(b==9){
        if(a<18){return 1}
        if(a<27){return 2}
        if(a<36){return 3}
        if(a<45){return 4}
        if(a<54){return 5}
        if(a<63){return 6}
        if(a<72){return 7}
        if(a<81){return 8}
        if(a<90){return 9}
        if(a<99){return 10}
        if(a<108){return 11}
        if(a<117){return 12}
        if(a<126){return 13}
        if(a<135){return 14}
        if(a<144){return 15}
        if(a<153){return 16}
        if(a<162){return 17}
        if(a<171){return 18}
        if(a<180){return 19}
        if(a<189){return 20}
        if(a<198){return 21}
        if(a<207){return 22}
    }
    if(b==10){
        if(a<20){return 1}
        if(a<30){return 2}
        if(a<40){return 3}
        if(a<50){return 4}
        if(a<60){return 5}
        if(a<70){return 6}
        if(a<80){return 7}
        if(a<90){return 8}
        if(a<100){return 9}
        if(a<110){return 10}
        if(a<120){return 11}
        if(a<130){return 12}
        if(a<140){return 13}
        if(a<150){return 14}
        if(a<160){return 15}
        if(a<170){return 16}
        if(a<180){return 17}
        if(a<190){return 18}
        if(a<200){return 19}
        if(a<210){return 20}
    }
    if(b==11){
        if(a<22){return 1}
        if(a<33){return 2}
        if(a<44){return 3}
        if(a<55){return 4}
        if(a<66){return 5}
        if(a<77){return 6}
        if(a<88){return 7}
        if(a<99){return 8}
        if(a<110){return 9}
        if(a<121){return 10}
        if(a<132){return 11}
        if(a<143){return 12}
        if(a<154){return 13}
        if(a<165){return 14}
        if(a<176){return 15}
        if(a<187){return 16}
        if(a<198){return 17}
        if(a<209){return 18}
    }
    if(b==12){
        if(a<24){return 1}
        if(a<36){return 2}
        if(a<48){return 3}
        if(a<60){return 4}
        if(a<72){return 5}
        if(a<84){return 6}
        if(a<96){return 7}
        if(a<108){return 8}
        if(a<120){return 9}
        if(a<132){return 10}
        if(a<144){return 11}
        if(a<156){return 12}
        if(a<168){return 13}
        if(a<180){return 14}
        if(a<192){return 15}
        if(a<204){return 16}
    }
    if(b==13){
        if(a<26){return 1}
        if(a<39){return 2}
        if(a<52){return 3}
        if(a<65){return 4}
        if(a<78){return 5}
        if(a<91){return 6}
        if(a<104){return 7}
        if(a<117){return 8}
        if(a<130){return 9}
        if(a<143){return 10}
        if(a<156){return 11}
        if(a<169){return 12}
        if(a<182){return 13}
        if(a<195){return 14}
        if(a<208){return 15}
    }
    if(b==14){
        if(a<28){return 1}
        if(a<42){return 2}
        if(a<56){return 3}
        if(a<70){return 4}
        if(a<84){return 5}
        if(a<98){return 6}
        if(a<112){return 7}
        if(a<126){return 8}
        if(a<140){return 9}
        if(a<154){return 10}
        if(a<168){return 11}
        if(a<182){return 12}
        if(a<196){return 13}
        if(a<210){return 14}
    }
    if(b==15){
        if(a<30){return 1}
        if(a<45){return 2}
        if(a<60){return 3}
        if(a<75){return 4}
        if(a<90){return 5}
        if(a<105){return 6}
        if(a<120){return 7}
        if(a<135){return 8}
        if(a<150){return 9}
        if(a<165){return 10}
        if(a<180){return 11}
        if(a<195){return 12}
        if(a<210){return 13}
    }
    if(b==16){
        if(a<32){return 1}
        if(a<48){return 2}
        if(a<64){return 3}
        if(a<80){return 4}
        if(a<96){return 5}
        if(a<112){return 6}
        if(a<128){return 7}
        if(a<144){return 8}
        if(a<160){return 9}
        if(a<176){return 10}
        if(a<192){return 11}
        if(a<208){return 12}
    }
    if(b==17){
        if(a<34){return 1}
        if(a<51){return 2}
        if(a<68){return 3}
        if(a<85){return 4}
        if(a<102){return 5}
        if(a<119){return 6}
        if(a<136){return 7}
        if(a<153){return 8}
        if(a<170){return 9}
        if(a<187){return 10}
        if(a<204){return 11}
    }
    if(b==18){
        if(a<36){return 1}
        if(a<54){return 2}
        if(a<72){return 3}
        if(a<90){return 4}
        if(a<108){return 5}
        if(a<126){return 6}
        if(a<144){return 7}
        if(a<162){return 8}
        if(a<180){return 9}
        if(a<198){return 10}
        if(a<216){return 11}
    }
    if(b==19){
        if(a<38){return 1}
        if(a<57){return 2}
        if(a<76){return 3}
        if(a<95){return 4}
        if(a<114){return 5}
        if(a<133){return 6}
        if(a<152){return 7}
        if(a<171){return 8}
        if(a<190){return 9}
        if(a<209){return 10}
    }
    if(b==20){
        if(a<40){return 1}
        if(a<60){return 2}
        if(a<80){return 3}
        if(a<100){return 4}
        if(a<120){return 5}
        if(a<140){return 6}
        if(a<160){return 7}
        if(a<180){return 8}
        if(a<200){return 9}
        if(a<220){return 10}
    }
    if(b==21){
        if(a<42){return 1}
        if(a<63){return 2}
        if(a<84){return 3}
        if(a<105){return 4}
        if(a<126){return 5}
        if(a<147){return 6}
        if(a<168){return 7}
        if(a<189){return 8}
        if(a<210){return 9}
    }
    if(b==22){
        if(a<44){return 1}
        if(a<66){return 2}
        if(a<88){return 3}
        if(a<110){return 4}
        if(a<132){return 5}
        if(a<154){return 6}
        if(a<176){return 7}
        if(a<198){return 8}
        if(a<220){return 9}
    }
    if(b==23){
        if(a<46){return 1}
        if(a<69){return 2}
        if(a<92){return 3}
        if(a<115){return 4}
        if(a<138){return 5}
        if(a<161){return 6}
        if(a<184){return 7}
        if(a<207){return 8}
    }
    if(b==24){
        if(a<48){return 1}
        if(a<72){return 2}
        if(a<96){return 3}
        if(a<120){return 4}
        if(a<144){return 5}
        if(a<168){return 6}
        if(a<192){return 7}
        if(a<216){return 8}
    }
    if(b==25){
        if(a<50){return 1}
        if(a<75){return 2}
        if(a<100){return 3}
        if(a<125){return 4}
        if(a<150){return 5}
        if(a<175){return 6}
        if(a<200){return 7}
        if(a<225){return 8}
    }
    if(b==26){
        if(a<52){return 1}
        if(a<78){return 2}
        if(a<104){return 3}
        if(a<130){return 4}
        if(a<156){return 5}
        if(a<182){return 6}
        if(a<208){return 7}
    }
    if(b==27){
        if(a<54){return 1}
        if(a<81){return 2}
        if(a<108){return 3}
        if(a<135){return 4}
        if(a<162){return 5}
        if(a<189){return 6}
        if(a<216){return 7}
    }
    if(b==28){
        if(a<56){return 1}
        if(a<84){return 2}
        if(a<112){return 3}
        if(a<140){return 4}
        if(a<168){return 5}
        if(a<196){return 6}
        if(a<224){return 7}
    }
    if(b==29){
        if(a<58){return 1}
        if(a<87){return 2}
        if(a<116){return 3}
        if(a<145){return 4}
        if(a<174){return 5}
        if(a<203){return 6}
    }
    if(b==30){
        if(a<60){return 1}
        if(a<90){return 2}
        if(a<120){return 3}
        if(a<150){return 4}
        if(a<180){return 5}
        if(a<210){return 6}
    }
    if(b==31){
        if(a<62){return 1}
        if(a<93){return 2}
        if(a<124){return 3}
        if(a<155){return 4}
        if(a<186){return 5}
        if(a<217){return 6}
    }
    if(b==32){
        if(a<64){return 1}
        if(a<96){return 2}
        if(a<128){return 3}
        if(a<160){return 4}
        if(a<192){return 5}
        if(a<224){return 6}
    }
    if(b==33){
        if(a<66){return 1}
        if(a<99){return 2}
        if(a<132){return 3}
        if(a<165){return 4}
        if(a<198){return 5}
        if(a<231){return 6}
    }
    if(b==34){
        if(a<68){return 1}
        if(a<102){return 2}
        if(a<136){return 3}
        if(a<170){return 4}
        if(a<204){return 5}
    }
    if(b==35){
        if(a<70){return 1}
        if(a<105){return 2}
        if(a<140){return 3}
        if(a<175){return 4}
        if(a<210){return 5}
    }
    if(b==36){
        if(a<72){return 1}
        if(a<108){return 2}
        if(a<144){return 3}
        if(a<180){return 4}
        if(a<216){return 5}
    }
    if(b==37){
        if(a<74){return 1}
        if(a<111){return 2}
        if(a<148){return 3}
        if(a<185){return 4}
        if(a<222){return 5}
    }
    if(b==38){
        if(a<76){return 1}
        if(a<114){return 2}
        if(a<152){return 3}
        if(a<190){return 4}
        if(a<228){return 5}
    }
    if(b==39){
        if(a<78){return 1}
        if(a<117){return 2}
        if(a<156){return 3}
        if(a<195){return 4}
        if(a<234){return 5}
    }
    if(b==40){
        if(a<80){return 1}
        if(a<120){return 2}
        if(a<160){return 3}
        if(a<200){return 4}
        if(a<240){return 5}
    }
    if(b==41){
        if(a<82){return 1}
        if(a<123){return 2}
        if(a<164){return 3}
        if(a<205){return 4}
    }
    if(b==42){
        if(a<84){return 1}
        if(a<126){return 2}
        if(a<168){return 3}
        if(a<210){return 4}
    }
    if(b==43){
        if(a<86){return 1}
        if(a<129){return 2}
        if(a<172){return 3}
        if(a<215){return 4}
    }
    if(b==44){
        if(a<88){return 1}
        if(a<132){return 2}
        if(a<176){return 3}
        if(a<220){return 4}
    }
    if(b==45){
        if(a<90){return 1}
        if(a<135){return 2}
        if(a<180){return 3}
        if(a<225){return 4}
    }
    if(b==46){
        if(a<92){return 1}
        if(a<138){return 2}
        if(a<184){return 3}
        if(a<230){return 4}
    }
    if(b==47){
        if(a<94){return 1}
        if(a<141){return 2}
        if(a<188){return 3}
        if(a<235){return 4}
    }
    if(b==48){
        if(a<96){return 1}
        if(a<144){return 2}
        if(a<192){return 3}
        if(a<240){return 4}
    }
    if(b==49){
        if(a<98){return 1}
        if(a<147){return 2}
        if(a<196){return 3}
        if(a<245){return 4}
    }
    if(b==50){
        if(a<100){return 1}
        if(a<150){return 2}
        if(a<200){return 3}
        if(a<250){return 4}
    }
    if(b==51){
        if(a<102){return 1}
        if(a<153){return 2}
        if(a<204){return 3}
    }
    if(b==52){
        if(a<104){return 1}
        if(a<156){return 2}
        if(a<208){return 3}
    }
    if(b==53){
        if(a<106){return 1}
        if(a<159){return 2}
        if(a<212){return 3}
    }
    if(b==54){
        if(a<108){return 1}
        if(a<162){return 2}
        if(a<216){return 3}
    }
    if(b==55){
        if(a<110){return 1}
        if(a<165){return 2}
        if(a<220){return 3}
    }
    if(b==56){
        if(a<112){return 1}
        if(a<168){return 2}
        if(a<224){return 3}
    }
    if(b==57){
        if(a<114){return 1}
        if(a<171){return 2}
        if(a<228){return 3}
    }
    if(b==58){
        if(a<116){return 1}
        if(a<174){return 2}
        if(a<232){return 3}
    }
    if(b==59){
        if(a<118){return 1}
        if(a<177){return 2}
        if(a<236){return 3}
    }
    if(b==60){
        if(a<120){return 1}
        if(a<180){return 2}
        if(a<240){return 3}
    }
    if(b==61){
        if(a<122){return 1}
        if(a<183){return 2}
        if(a<244){return 3}
    }
    if(b==62){
        if(a<124){return 1}
        if(a<186){return 2}
        if(a<248){return 3}
    }
    if(b==63){
        if(a<126){return 1}
        if(a<189){return 2}
        if(a<252){return 3}
    }
    if(b==64){
        if(a<128){return 1}
        if(a<192){return 2}
        if(a<256){return 3}
    }
    if(b==65){
        if(a<130){return 1}
        if(a<195){return 2}
        if(a<260){return 3}
    }
    if(b==66){
        if(a<132){return 1}
        if(a<198){return 2}
        if(a<264){return 3}
    }
    if(b==67){
        if(a<134){return 1}
        if(a<201){return 2}
    }
    if(b==68){
        if(a<136){return 1}
        if(a<204){return 2}
    }
    if(b==69){
        if(a<138){return 1}
        if(a<207){return 2}
    }
    if(b==70){
        if(a<140){return 1}
        if(a<210){return 2}
    }
    if(b==71){
        if(a<142){return 1}
        if(a<213){return 2}
    }
    if(b==72){
        if(a<144){return 1}
        if(a<216){return 2}
    }
    if(b==73){
        if(a<146){return 1}
        if(a<219){return 2}
    }
    if(b==74){
        if(a<148){return 1}
        if(a<222){return 2}
    }
    if(b==75){
        if(a<150){return 1}
        if(a<225){return 2}
    }
    if(b==76){
        if(a<152){return 1}
        if(a<228){return 2}
    }
    if(b==77){
        if(a<154){return 1}
        if(a<231){return 2}
    }
    if(b==78){
        if(a<156){return 1}
        if(a<234){return 2}
    }
    if(b==79){
        if(a<158){return 1}
        if(a<237){return 2}
    }
    if(b==80){
        if(a<160){return 1}
        if(a<240){return 2}
    }
    if(b==81){
        if(a<162){return 1}
        if(a<243){return 2}
    }
    if(b==82){
        if(a<164){return 1}
        if(a<246){return 2}
    }
    if(b==83){
        if(a<166){return 1}
        if(a<249){return 2}
    }
    if(b==84){
        if(a<168){return 1}
        if(a<252){return 2}
    }
    if(b==85){
        if(a<170){return 1}
        if(a<255){return 2}
    }
    if(b==86){
        if(a<172){return 1}
        if(a<258){return 2}
    }
    if(b==87){
        if(a<174){return 1}
        if(a<261){return 2}
    }
    if(b==88){
        if(a<176){return 1}
        if(a<264){return 2}
    }
    if(b==89){
        if(a<178){return 1}
        if(a<267){return 2}
    }
    if(b==90){
        if(a<180){return 1}
        if(a<270){return 2}
    }
    if(b==91){
        if(a<182){return 1}
        if(a<273){return 2}
    }
    if(b==92){
        if(a<184){return 1}
        if(a<276){return 2}
    }
    if(b==93){
        if(a<186){return 1}
        if(a<279){return 2}
    }
    if(b==94){
        if(a<188){return 1}
        if(a<282){return 2}
    }
    if(b==95){
        if(a<190){return 1}
        if(a<285){return 2}
    }
    if(b==96){
        if(a<192){return 1}
        if(a<288){return 2}
    }
    if(b==97){
        if(a<194){return 1}
        if(a<291){return 2}
    }
    if(b==98){
        if(a<196){return 1}
        if(a<294){return 2}
    }
    if(b==99){
        if(a<198){return 1}
        if(a<297){return 2}
    }
    if(b==100){
        if(a<200){return 1}
        if(a<300){return 2}
    }
    if(b<=200 && a<=200){
        return 1
    }
    var result=0
    var counter=b
    for(;a>=counter;counter=add(counter,b)){
        result=add(result,1)
    }
    return result
}
\$\endgroup\$
  • \$\begingroup\$ +1 Nice job. Did not thought about this way. \$\endgroup\$ – Johannes Kuhn Sep 14 '13 at 20:43
  • \$\begingroup\$ Your answer resembles Mechanical Snail's answer to the division by 3 problem. \$\endgroup\$ – Joe Z. Sep 14 '13 at 20:45
  • 1
    \$\begingroup\$ Ok, now we have a tie. Who wins? @JoeZ. You should accept the answer with has the minimum additions. \$\endgroup\$ – Johannes Kuhn Sep 14 '13 at 20:48
  • 4
    \$\begingroup\$ My question doesn't limit inputs from a from 1 to 200, it only says it will judge the score based on the total additions from that range of inputs. It still has to work for integers above 200. \$\endgroup\$ – Joe Z. Sep 15 '13 at 16:51
  • 1
    \$\begingroup\$ For example, the current edition of the answer does just that. \$\endgroup\$ – Joe Z. Sep 15 '13 at 16:54
6
\$\begingroup\$

Tcl, 0 additions

proc divide {a b} {
    set sa [string repeat . $a]
    set sb [string repeat . $b]
    set sr ""
    while 1 {
        append sc $sb
        if {[string le $sc]>[string le $sa]} break
        append sr .
    }
    return [string le $sr]
}

Why not use strings?

\$\endgroup\$
  • \$\begingroup\$ Alright, give me some time to revise the question statement. \$\endgroup\$ – Joe Z. Sep 14 '13 at 19:05
  • \$\begingroup\$ Hey, too many loopholes. \$\endgroup\$ – Johannes Kuhn Sep 14 '13 at 19:05
  • \$\begingroup\$ This one is pretty clever, actually. \$\endgroup\$ – Joe Z. Sep 14 '13 at 19:17
  • \$\begingroup\$ This looks good to me. Append is akin to addition, but it is not quite the same. I Joined lists, using a similar logic based on tallies. \$\endgroup\$ – DavidC Sep 15 '13 at 1:15
3
\$\begingroup\$

Haskell 0 additions, 29 bytes

n/m=[i|i<-[0..],_<-[1..m]]!!n

this redefines the division operator (/). it works by making a list of 0 to infinity where each item is repeated m times, and then choosing the nth element of the list (using a 0-based index).

\$\endgroup\$
  • 1
    \$\begingroup\$ Hey, can you add a description of what this code does? \$\endgroup\$ – Beta Decay Oct 6 '14 at 15:51
  • \$\begingroup\$ if this was code golf, you would have surely won.. \$\endgroup\$ – proud haskeller Oct 6 '14 at 21:09
  • \$\begingroup\$ What about using ([0..]>>=replicate m)!!n. it's almost the same \$\endgroup\$ – proud haskeller Oct 7 '14 at 15:11
2
\$\begingroup\$

Use this implementation in java, 199206 additions

public int divide(int a, int b){
    int counter = 0;
    int c = 0;
    if(b==1){
        return a;
    }
    if(a==b){
        return 1;
    }
    else{
        boolean done = false;
        while(!done){
            c = add(c, b);
            if(a<c){
                done = true;
            }
            counter = add(counter,1);
        }
        return counter;

    }
}

Following are the helper functions

public static void main(String[] args) {
    Main main = new Main();

    for(int a = 1; a<=200; a++){    
        for(int b=1;b<=a;b++){
            main.divide(a, b);
        }
    }

    System.out.println("Number of additions: "+numberOfAdds);
}

public int add(int a, int b){
    numberOfAdds++;
    return (a+b);
}
\$\endgroup\$
  • \$\begingroup\$ yes, thanks for pointing out, corrected it in the answer \$\endgroup\$ – Anurag Sep 15 '13 at 17:55
2
\$\begingroup\$

Python - 0 additions

from itertools import repeat, count

def divide(a, b):
    i = repeat(0, a)
    try:
        for j in count():
            for k in repeat(0, b):
                next(i)
    except:
        return j

This uses an iterator of length a, and consumes it in groups of b until StopIteration is raised. At this point j contains the result.

\$\endgroup\$
2
\$\begingroup\$

My solution is C/C++ code and it makes many additions (200402), but anyway...

#include <iostream>

int total = 0;

int sum(int a, int b)
{
    ++total;
    return a + b;
}

int divide(int a, int b)
{
    int x = 1;
    if (a < b)
        return 0;
    else
        return sum(x, divide(sum(a, -b), b));
}

int main()
{
    for (int i = 1; i <= 200; ++i)
        for (int j = 1; j <= 200; ++j)
        {
            if (divide(i, j) != (i / j))
                std::cout << "Failure: a=" << i << " b=" << j << "\n";
        }

    std::cout << "Total additions: " << total << std::endl;
    system("pause");
}

And the output is:

Total additions: 200402
Press any key to continue . . .
\$\endgroup\$
1
\$\begingroup\$

Python, 320703 additions

def divide(a, b):
    quotient = 0
    c = 0
    d = 0
    while add(d, b) <= a:
        c = add(c, 1)
        d = add(d, b)
    return c

As always, a last-place reference answer. This simply adds 1 to a "quotient" and b to a "remultiplication" variable until it hits a.

Here is the debugging code:

add_used = 0

def add(a, b):
    global add_used
    add_used += 1
    return a + b

for a in range(1, 201):
    for b in range(1, a+1):
        print "%d / %d = %d" % (a, b, divide(a, b))

print "Additions used:", add_used
\$\endgroup\$
1
\$\begingroup\$

Tcl, 0 additions.

Well, I had to find a way that does not use other data structures but is still not what you want:

# coroutine counter.
proc ccnt {} {yield [info level]; ccnt}
# add implementation without add.
proc cadd {a b} {
    set last 2
    coroutine cadda ccnt
    coroutine caddb ccnt
    while {[cadda]<=$a} {}
    while {[caddb]<=$b} {set last [cadda]}
    rename cadda {}
    rename caddb {}
    return $last
}

proc divide {a b {c 0}} {
    if {$c == 0} {set c $b} {set c [cadd $b $c]}
    if {$c>$a} {tailcall info level}
    divide $a $b $c
}

Uses the current stack size of different green threads.

\$\endgroup\$
  • \$\begingroup\$ Nope, this is perfect. \$\endgroup\$ – Joe Z. Sep 14 '13 at 19:46
  • \$\begingroup\$ Really? I think I'll rewrite it a bit using coroutines. \$\endgroup\$ – Johannes Kuhn Sep 14 '13 at 19:51
  • \$\begingroup\$ And again: score 0 \$\endgroup\$ – Johannes Kuhn Sep 14 '13 at 20:05
  • \$\begingroup\$ Dammit D: [Well, that's as far as I'm willing to go :<] \$\endgroup\$ – Joe Z. Sep 14 '13 at 20:17
  • \$\begingroup\$ +1 for you as well, overflowing the stack for relatively trivial problems that happen to lie outside the area that is being judged is really in the spirit of totally ****** ** solutions! \$\endgroup\$ – aaaaaaaaaaaa Sep 14 '13 at 20:50
1
\$\begingroup\$

C++ ,100201

for(int a = 1; a<=200; a++){    
        for(int b=1;b<=a;b++){
    iter1 = iter2 = b; 
cout<<a<<" "<<b<<endl;   

c1 =0;
while(iter1 <= a)
{
    iter1 = iter1 + iter2;
    c1 ++;
    nadd++;
}
cout<<"Quotient : "<<c1;
cout<<" Remainder :"<<a - (iter1 - iter2)<<endl;    
}  
}
cout<<"total of add "<<nadd;
\$\endgroup\$
  • \$\begingroup\$ If a < b the result should be 0, not an error. \$\endgroup\$ – Joe Z. Sep 15 '13 at 6:34
  • \$\begingroup\$ @JoeZ. ok thanks , is it fine now? \$\endgroup\$ – p.j Sep 15 '13 at 8:11
  • \$\begingroup\$ break should be continue. \$\endgroup\$ – Joe Z. Sep 15 '13 at 8:27
  • \$\begingroup\$ inner loop should break I think , because once a < b then inner loop is increasing b then you should I do for other b's...actually that is redundant so I should remove that statement, a < b will never happen in this case... \$\endgroup\$ – p.j Sep 15 '13 at 8:34
  • \$\begingroup\$ Oh wait, never mind, I see what you mean. (I got confused by the order of the numbers.) \$\endgroup\$ – Joe Z. Sep 15 '13 at 16:52
1
\$\begingroup\$

Mathematica 100201 additions

This adds the divisor, b, to c (which is initialized at 0) as long as the running total is less than or equal to the dividend, a. It also appends the current value of c to a list, t, without performing any arithmetic operation.

When the While loop terminates the function outputs the length of t, which will correspond exactly to the quotient of integer division. Thus the number of additions for any given divide[a,b] will equal precisely the quotient.

100201 is the sum of the quotients in the 200 by 200 table. That's how many times c was incremented by b. No other additions were required. Only positive integers were used.

divide[a_, b_] := Module[{c = 0, t = {}}, While[c <= a, t = Append[t, c]; c += b]; 
Length[Rest@t]]

It's more efficient to make a lookup table, after which each search will be almost instantaneous.

n = 200;
d[a_, b_] := Module[{c = 0, t = {}}, While[c <= a, t = Append[t, c]; c += b]; 
Length[Rest@t]]
quotients = PadRight[#, n] & /@ Table[d[i, j], {i, 1, n}, {j, 1, i}];
divide[a_, b_] := quotients[[a, b]]

Usage

divide[97, 13]

7

\$\endgroup\$
  • 1
    \$\begingroup\$ So more or less my string based solution? Ohh, and can you explain the n++ thing? Looks like addition for me. \$\endgroup\$ – Johannes Kuhn Sep 14 '13 at 22:22
  • 1
    \$\begingroup\$ Yeah, the successor function counts as addition, without which it's not allowed. \$\endgroup\$ – Joe Z. Sep 14 '13 at 22:28
  • \$\begingroup\$ @Johannes Kuhn. I removed the n++, which was totally unnecessary. From what I can tell, (I don't know TCL), my solution is like yours, but stores the elements together in multi-sets rather then in strings. \$\endgroup\$ – DavidC Sep 15 '13 at 1:13
  • 1
    \$\begingroup\$ What about no other data constructs besides numbers? \$\endgroup\$ – ugoren Sep 15 '13 at 8:08
  • \$\begingroup\$ @Ugoren Don't you think a base one number system qualifies as being about numbers? The arguable issue, I think, is whether or not joining constitutes adding. \$\endgroup\$ – DavidC Sep 15 '13 at 13:56
1
\$\begingroup\$

R - 0 addition

divide<-function(a,b){
    options(warn=-1)
    A<-matrix(1:b,nrow=a,ncol=1)
    length(split(A,A)[[b]])
    }

Uses R vector recycling.
Second line creates a matrix of length a populated by a vector of length bwhich is recycled until reaching length a.
Third line split the matrix according to its value and return the length of the last element (hence the result of the integer division of a by b).
Populating a matrix with a vector which length is not a multiple of the length of the matrix throws a warning but if we suppress warning beforehand (line 1) it works.

To give a concrete example if we divide 5 by 3, A will be a vector containing 1 2 3 1 2 (i. e. 1 2 3 recycled to a length 5). The result of the splitting operation will be a list with the first element containing 1 1, the second 2 2 and the third 3 (since there is only one 3 in A). The result is therefore 1.

\$\endgroup\$
  • \$\begingroup\$ A Matix sounds like a different data structure than a number. \$\endgroup\$ – Johannes Kuhn Sep 17 '13 at 7:11
  • \$\begingroup\$ Ah indeed I missed the part where it was specified that the only data construct allowed was numbers. My bad. I answered after the edit but read the question before :) \$\endgroup\$ – plannapus Sep 17 '13 at 7:29
1
\$\begingroup\$

In Ruby,

def divide(a,b)
  n, d = 'x' * a, 'x' * b
  l = []
  (l << 'x'; d << 'x' * b) while n.size >= d.size
  l.size
end  

I don't know TCL, but I suspect this is the same approach as @Johannes ' (first) answer.

\$\endgroup\$
  • \$\begingroup\$ What do the * and << do? I'm not familiar with Ruby. \$\endgroup\$ – Joe Z. Sep 25 '13 at 4:02
  • \$\begingroup\$ @Joe: d = 'x' * 5 => "xxxxx". a << b appends string b to string a. Here, d = "xxx" and d << 'x' results in d = "xxxx". \$\endgroup\$ – Cary Swoveland Sep 26 '13 at 0:16
1
\$\begingroup\$

Java: 92 987 additions

I use binary recursion, that a/b == 2 * a/(2b) + maybe 1. For that divisor and remainder are needed. There would normally be a subtraction a % (2b) - b, but that is resolved by holding the remainder as (rem, remNegative). And 2b = b+b of course.

static int add_used;

static int add(int a, int b) {
    if (a == 0)
        return b;
    if (b == 0)
        return a;
    ++add_used;
    return a + b;
}

private static class DivRem {
    int div;
    int rem;
    int remNegative;

    DivRem(int div, int rem) {
        this.div = div;
        this.rem = rem;
    }
}

public static int divide(int a, int b) {
    add_used = 0;
    return divrem(a, b).div;
}

public static DivRem divrem(int a, int b) {
    if (b > a) {
        return new DivRem(0, a);
    }
    DivRem dr = divrem(a, add(b, b));
    dr.div = add(dr.div, dr.div);
    if (dr.rem >= add(b, dr.remNegative)) {
        dr.div = add(dr.div, 1);
        //dr.rem = add(dr.rem,  -b);
        dr.remNegative = add(dr.remNegative,  b);
    }
    return dr;
}

private static void test(int a, int b) {
    boolean okay = a/b == divide(a, b);
    System.out.printf("%d / %d = %d :: %d : #%d  %s%n", a, b, a/b,
        divide(a, b), add_used, okay);
}

public static void main(String[] args) {
   //test(2352, 324);
   int n = 0;
   for (int a = 1; a <= 200; ++a) {
       for (int b = 1; b <= a; ++b) {
           //test(a, b);
           divide(a, b);
           n += add_used;
       }
   }
   System.out.println("Additions: " + n);
}
\$\endgroup\$
  • \$\begingroup\$ And how many divisions does it use? \$\endgroup\$ – Doorknob Sep 28 '13 at 16:27
  • \$\begingroup\$ @Doorknob 92987 (did not see the for-for). \$\endgroup\$ – Joop Eggen Sep 30 '13 at 12:12
  • \$\begingroup\$ One remark: this does count neither 0+x nor x+0: so ~100k additions. \$\endgroup\$ – Joop Eggen Oct 1 '13 at 23:08
0
\$\begingroup\$
//a lies between 1 and 200, b lies between 1 and a.

int divide(int a,int b){
int x=a,y=b;
int count=1;
while(y<x){
y+=y;
count++;
}
return count;
}
\$\endgroup\$
  • 3
    \$\begingroup\$ And how many additions are that? \$\endgroup\$ – Johannes Kuhn Sep 15 '13 at 14:11
0
\$\begingroup\$

C# - 0 additions

using System.Collections.Generic;
using System.Linq;

static int Divide(int a, int b)
{
    var ints = new List<int>(a);
    while (ints.Count < a)
        ints.AddRange(Enumerable.Range(1, b));

    return ints.Select((x, i) => x == b && i < a).Count(x => x);
}

Populates a list of integers with 1..b repeated a times. The number of times b appears (except for the occurrence with an index > a) is the result.

I'm not sure if the list is allowed by the rules, but I'm submitting this in the spirit of the other posts which aren't taking the rules all that seriously (after all, not using addition at all is basically bypassing the challenge altogether).

\$\endgroup\$
  • \$\begingroup\$ Yeah, following the "spirit" of the challenge was pretty much abandoned by this point. \$\endgroup\$ – Joe Z. Sep 17 '13 at 4:38
  • \$\begingroup\$ There is 1 solution out there that takes all the rules seriously and has 0 additions. \$\endgroup\$ – Johannes Kuhn Sep 17 '13 at 7:14
  • \$\begingroup\$ @JohannesKuhn: That's debatable. The challenge is to do division using addition. If we don't use addition, we're not really doing the challenge... \$\endgroup\$ – Igby Largeman Sep 17 '13 at 7:45
0
\$\begingroup\$

C — 85591 Additions

Here we go. I think this might be optimal. It uses a technique of "reverse division" whereby through long multiplication it builds up the largest number q such that q * b <= a, using only + and <=. It is very, very fast.

#include <stdio.h>
#include <assert.h>

// Division function.
q,u,v,z=0;s(a,b){return!a?b:!b?a:(z++,a+b);}
d(a,b,p){if((v=s(b,b))<=a)d(a,v,s(p,p));if((v=s(u,b))<=a)u=v,q=s(p,q);}
divide(a,b){u=q=0;d(a,b,1);return q;}

// Test driver.
main(){for(int a=1;a<=200;a++)for(int b=1;b<=a;b++)assert(divide(a,b)==q);
printf("%d additions\n",z);}

Notes:

  1. s(a,b) returns the sum a+b and increments counter variable z each time an addition is performed. If either a or b is zero, the unnecessary addition is avoided.
  2. d(a,b,p) is a recursive function to build up the internal portions for comparison and addition. It uses global variables q, u, and v. Maximum recursion depth is the number of bits in a, and the recursion is linear rather than a tree. (Note: the b in this function is the original b multiplied by a power of 2.)
  3. divide(a,b) returns floor(a/b) as required.
  4. Compiles with warnings (because code is golfed). Runs fine.
\$\endgroup\$
0
\$\begingroup\$

J, 0 additions, 14 bytes

Inspired by Alexei Kopylov's answer.

f=:[{]#i.@>:@[

Uses no maths at all:

f=:                    NB. define function f
             [         NB. take left argument,
          >:@          NB. increment it,
       i.@             NB. generate the list [0..left arg+1)
     ]#                NB. replicate each item in the list by the right argument
                       NB. (so if ]=2, list becomes 0 0 1 1 2 2 3 3 ...)
   [{                  NB. select the ['th item from that list.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.