# Questions tagged [integers]

Questions about properties of, working with and algorithms on integers.

138 questions
Filter by
Sorted by
Tagged with
24 views

### Integer-only computation rounds down fractions in division require extra work?

In integer-only computation, a fraction like 5/2 is rounded down to 2. Is this any extra work at the ALU level, or, is the way it does division, at the level of logical gates, automatically outputting ...
30 views

### What does it mean for an integer to belong to the halting problem?

I have come across the description of a function $F: \mathbb{N} \to \mathbb{N}$ where the function is defined one way for $n \in \mathcal{H}$ and another way for $n \notin \mathcal{H}.$ In this ...
53 views

### How to represent $x$ in hexadecimal form where $x=2^n$?

When a value $x$ is a power of $2$, that is, $x = 2^n$ for some nonnegative integer n, we can readily write $x$ in hexadecimal form by remembering that the binary representation of $x$ is simply $1$ ...
60 views

### Efficient Algorithm to Find the Closest Integer Representation, in the Form $A\times\frac{N}{D}$ for a Value

The Problem I am working on a problem that boils down to finding the closest representation of an arbitrary number ($x$) in the form: $$x = A\times\frac{N}{D}$$ Where $A$ is a 32-bit integer, and $N$ ...
42 views

### How to rewrite a function such that integer division is applied before multiplication

Given the following function $$f(x,y) = (x \cdot y + 999)\; \text{div} \; 1000$$ where $x \in \{0, 1, 2, \dots, 2^{63}-1\}$, $y \in \{1, 2, 3, \dots, 500\}$, and the div operator is defined to round ...
44 views

113 views

### Mistake in the Algorithm Design Manual?

Look at this excerpt from the Algorithm Design Manual by Skiena, 2nd Edition The sum of the first $n$ even integers? Surely, the two sums given do not include only even numbers, right? Is this a ...
304 views

### Linear time multiplication on RAM machine?

This page says following: Integer Multiplication has an O-optimal linear-time algorithm on a RAM or SMM Is this page fooling me or how can we multiply 2 numbers in linear time (bitwise complexity) ...
137 views

### Compress 32 bit integer into a normalized float

and sorry if this is a duplicate of some sort, my poor technical vocabulary doesn't get me very far with google. I am trying to implement some well-known PRNG algorithms. For the time, the algorithm ...
95 views

### How to find the closest N to the power of X to the given number?

Let's say we have number 4920 and we want to find the closest $n^x$ to 4920 2 ^ 12 = 4096 but it's not the closest possible $n^x$, for example 17 ^ 3 = 4913 is closer to 4920 The question is, how do ...
89 views

### Swap elements using integer addition and multiplication gates

I need to swap two integers using only integer addition and multiplication gates. I can't subtract them. I'm dealing with a sorting network, so I need to compare and swap. The compare and swap ...
I want to iterate through the numbers $0,1,2,\dots,n-1$ in some order, where each number in the sequence differs by only one bit from the previous bit. I'm going to be using each number as an index ...