flat assembler
Message board for the users of flat assembler.

Index > Heap > Subtract with increase

Author
Thread Post new topic Reply to topic
l4m2



Joined: 15 Jan 2015
Posts: 648
l4m2
Let's only use these code:
Code:
x=0    
Code:
x=x+1    
Code:
repeat x
  ...
end repeat    

We can let output=input1+input2 (assuming all the value are integers more than or equal to zero)
Code:
output=0
repeat input1
  output=output+1
end repeat
repeat input2
  output=output+1
end repeat    
or output=input1*input2
Code:
output=0
repeat input1
  repeat input2
    output=output+1
  end repeat
end repeat    

1. How to let output=input-1? (assume input>0)
2. How to let output=input1-input2? (assume input1>=input2)

I can now do 2. in O(input1+input2*input2). Is there a better solution?

Update: Now done in O(input1+input2)


Last edited by l4m2 on 03 Sep 2016, 12:01; edited 3 times in total
Post 30 Aug 2016, 09:57
View user's profile Send private message Reply with quote
YONG



Joined: 16 Mar 2005
Posts: 8000
Location: 22° 15' N | 114° 10' E
YONG
If you change the title from "Subtact" to "Subtract", you may get some tangible replies.

Wink
Post 31 Aug 2016, 03:09
View user's profile Send private message Visit poster's website Reply with quote
l4m2



Joined: 15 Jan 2015
Posts: 648
l4m2
YONG wrote:
If you change the title from "Subtact" to "Subtract", you may get some tangible replies.

Wink
Done
Post 31 Aug 2016, 05:44
View user's profile Send private message Reply with quote
Furs



Joined: 04 Mar 2016
Posts: 1471
Furs
I don't think that's possible without utilizing more operations (such as negation or bit flipping), or overflow.

In case of overflow, however, you'll need more constants (such as the highest unsigned integer available) and not just x=0...

Of course this won't work in actual FASM, if that's what you're after, I assumed you used pseudo code to demonstrate your ideas.

For example with overflow on 16-bit numbers, output=input1-1:

Code:
output=0
repeat input1
  output=output+1
end repeat
repeat 65535
  output=output+1
end repeat    
Post 31 Aug 2016, 10:47
View user's profile Send private message Reply with quote
l4m2



Joined: 15 Jan 2015
Posts: 648
l4m2
Furs wrote:
I don't think that's possible without utilizing more operations (such as negation or bit flipping), or overflow.

In case of overflow, however, you'll need more constants (such as the highest unsigned integer available) and not just x=0...
The author of question 1 gave this answer:
Code:
temp=0
repeat input
  output=temp ;The origional requirement allow to use x=y but here we should let x=0 and add 1 for y times instead
  temp=temp+1
end repeat    
Post 31 Aug 2016, 10:53
View user's profile Send private message Reply with quote
l4m2



Joined: 15 Jan 2015
Posts: 648
l4m2
I think it can't be faster than O(input1+input2) for numbers can only be used to repeat
Post 03 Sep 2016, 12:04
View user's profile Send private message Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  


< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You can attach files in this forum
You can download files in this forum


Copyright © 1999-2020, Tomasz Grysztar. Also on YouTube, Twitter.

Website powered by rwasa.