4 ms·
Comparisons can be done via subtraction. Result has no bit set = both terms equal Result's sign bit is set = second term bigger Result's sign bit isn't set = f
by MrYellowP 6y ago
Comparisons can be done via subtraction.
Result has no bit set = both terms equal
Result's sign bit is set = second term bigger
Result's sign bit isn't set = first term bigger
Multiplying by the result of comparisons (aka 0 and 1, as you state) is actually a common performance optimization. Does not work for everything, but when it works it works well.
- giomasce 6y agoYes, but you can't branch on the result, because you don't know if the result is zero or not. So your program needs to have fixed control flow, i.e., you cannot implement arbitrary programs.
- dlubarov 6y agoThere isn't branching in the traditional sense, but we can work around it. Instead of doing result = if condition { a } else { b } in circuit programming, we normally do result = condition * a + (1 - condition) * b
- giomasce 6y agoSure, that was already mentioned on another comment, but that's not enough for proper branching. You also need while loops. See also comment https://news.ycombinator.com/item?id=24018284 https://news.ycombinator.com/item?id=24018284.
- heavenlyblue 6y agoIf you constrain your computer to always take the same amount of time to execute any while loop (which a homomorphic computer needs to do not to leak any data), your computer would also have unbounded circuitry complexity and thus it’s not any better. Also unbounded loops can’t practically finish even on a Turing machine :)
- giomasce 6y agoThat's my point: not any Turing machine can be implemented with FHE, because FHE must have bounded execution time.
- heavenlyblue 6y agoYou can either say “a Turing machine can not be implemented” or “it can” but never “not any Turing machine” because there isn’t any types of a Turing machine - just a single one.
- heavenlyblue 6y agoYou don’t need to branch, you execute both branches at the same time.