Tag Info

New answers tagged

1

Reducing exponentiation to squaring and occasional multiplication seems to be fast, see Exponentiation by Squaring. It uses $$ x^n = \begin{cases} x \, ( x^{2})^{(n - 1)/2}, & \mbox{if } n \mbox{ is odd} \\ (x^{2})^{n/2} , & \mbox{if } n \mbox{ is even}. \end{cases} $$ The squaring is done by $x^2 = x * x$. In Henry S. Warren's "Hacker's Delight", ...


0

And if you want to square (or multiply) very large numbers, there is the Karatsuba algorithm: http://en.wikipedia.org/wiki/Karatsuba_algorithm


1

Here's a reference that I found: http://en.wikipedia.org/wiki/Modular_exponentiation#Right-to-left_binary_method The most intuitive algorithm that I can think of for squaring binary numbers involves appending zeros and adding. As an example, say you want to square $101101$. To do so, note the position of each $1$ in the number (this can be done ...


4

This all boils down to the concept of positional notation. For example, consider the number $19$ (in base $10$), which in base $2$ becomes $10011$. To understand why, you need to understand what this notation mean: $$ 19_{10} = \color{lime}{1}\color{green}{0}\color{olive}{0}\color{grey}{1}1_2 := 1 \cdot 2^0 + \color{grey}{1} \cdot 2^1 + \color{olive}{0} ...


1

PolynomialQuotientRemainder[x^22+x^18+x^17+x^14+x^12,x^8+x^2+x+1,x,Modulus->2] {x+x^2+x^7+x^8+x^9+x^10+x^14,x+x^4+x^7} Update for move to math: Well, now that it's here, the Mathematica answer doesn't seem quite as useful anymore. The answer is that you use the same long division you learned in elementary school. The only difference is that now ...


1

I’ll get you started. Start at the bottom: the leaves have empty subtrees, so the value of each leaf is simply the integer stored in it. Now go up a level and work on the four max nodes just above the leaves. each of them is the root of a small tree with $3$ nodes. For the first one, for instance, we have this tree: 0 / \ ...


0

I don't see where the "desired degree" comes into your question. Leaving that aside, there is further the issue of what coefficient ring you are intending to use -- it seems like $\mathbb{F}_2$ would be most appropriate, but maybe you mean $\mathbb{Z}$. For now I'll assume that you are working over $\mathbb{Z}$. The first step is to create the ...


1

Hint: Whatever the first $N-1$ bits are, the probability that $X$ is odd is $\frac{1}{2}$.


0

There's no need to guess: \begin{align} 120&=2\cdot 60+0\\ 60&=2\cdot 30+0\\ 30&=2\cdot 15+0\\ 15&=2\cdot 7+1\\ 7&=2\cdot 3+1\\ 3&=2\cdot 1+1\\ 1&=2\cdot 0+1 \end{align} So $$ 120=\texttt{1111000}=0\cdot1+0\cdot2+0\cdot4+1\cdot8+1\cdot16+1\cdot32+1\cdot64 $$ If you want to use eight bits, then you can pad with zeros on the left: ...


1

Do you already know the answer to this question? You really should indicate that if you do. I presume the microbiologist determines the $7$-bit representation of the sample number, and sends all samples with the highest-order bit set into vial $1$, the second-highest-order bit into vial $2$, and so on, with those samples with the lowest-order bit set into ...


2

There is the relationship $(a\wedge b)\oplus (a\vee b) \oplus (a\oplus b)=0$ which holds for all $a$ and $b$. Or, equivalently, any two of $a\wedge b$, $a\vee b$, and $a\oplus b$ will produce the third upon combining with $\oplus$.


3

A simple explanation turns on the apparent randomness of the base-$b$ digits of sufficiently large powers of two, in the sense that they tend to behave like random samples. (However, this leaves the apparent randomness unexplained.) Thus, let $S_k$ denote the multiset of digits appearing in the numeral of $2^k$, and let $n_k$ be their number; i.e., $n_k = ...


1

Are you familiar with the definitions of reflexive, symmetric and transitive relations? A reflexive relation is a binary relation on a set for which every element is related to itself. As you can clearly see $(0,0),(1,1)$ etc. are not contained in your relation, so it is not reflexive. A relation is symmetric if $aRb \implies bRa$. Once again, ...


0

A relation is reflexive $\iff$ $\forall_{\alpha}(\alpha \in A)$$(\langle\alpha,\alpha\rangle \in T)$. This is clearly not the case for T. A relation is symmetric $\iff$ $\forall_{\alpha, \beta}(\alpha \in A)([\langle\alpha,\beta\rangle\in T] \rightarrow [\langle\beta,\alpha\rangle \in T])$. This isn't the case for T either. A relation is transitive $\iff$ ...


0

To be Reflexive you should have (0,0) (1,1) (2,2) (3,3) To be symmetric if you have (0,1), then you should have (1,0) To be transitive if you have (1,2) (2,4), then you should have (1,4) To answer your question NO for Symmetric and Reflexive Yes for transitive because no counter example


1

The short answer to "what does this mean": To say that $x$ is related to $y$ by $R$ (also written $x \mathbin {R} y$, especially if $R$ is a symbol like "$<$") means that $(x,y) \in R$. (Well, there may be some ambiguity about whether $(x,y) \in R$ is read as "$x$ is related to $y$ by $R$" or "$y$ is related to $x$ by $R$", but it doesn't matter in this ...


1

Let $\sim$ be an equivalence relation (reflexive, symmetric, transitive) on a set $S$. The equivalence class under $\sim$ of an element $x \in S$ is the set of all $y \in S$ such that $x \sim y$. An equivalence relation will partition a set into equivalence classes; the quotient set $S/\sim$ is the set of all equivalence classes of $S$ under $\sim$. At the ...


0

The equivalence classes are $\{0,4\},\{1,3\},\{2\}$. to see this you should first check your relation is indeed an equivalence relation. After this find all the elements related to $0$. Then pick the next smallest number not related to zero and find all the elements related to it and so on until you have processed each number.


0

You have to prove that $R$ is reflexive, symmetric and transitive. 1)Reflexive: Clear since if we have the same set then least elements are equal. So, $SRS$. 2) Symmetric: Suppose $SRT$. Then least element of $S$ equals least element of $T$. Hence, least element of $T$ equals least element of $S$. So, $TRS$. 3) Transitive: Suppose $SRT$ and $TRU$. Then ...


0

Another solution is to find the common "left header" of m and n. Bitwise AND of this common left header definitely results in 1, while the remaining right part results in 0 since at least 1 bit in a number between m and n is 0. Below is the Python code: def rangeBitwiseAnd(self, m, n): shift = 0 #find the common left header (or, same prefix) of m ...


1

Checking is easy: If $$x=0.{\bf q}{\bf p}{\bf p}{\bf p}{\bf p}\ldots\ ,\tag{1}$$ where the preperiod ${\bf q}$ and the period ${\bf p}$ are binary strings of length $r$ and $s$, respectively, then $$2^rx={\bf q}.{\bf p}{\bf p}{\bf p}{\bf p}\ldots$$ and consequently $$(2^r-1)x={\bf q}.{\bf p}-0.{\bf q}\ .$$ It follows that $$x={{\bf q}.{\bf p}-0.{\bf q}\over ...


0

Take the example of ⅔ = 0.1010101010... divide by 2: = 0.0101010101... add them up 1 = 0.1111111111 ... So even if we had no idea that the binary, call it b, was ⅔ initially we would know now that b + b/2 =1 and so b=⅔ For ⅖ b = 0.011001100110 ... 2b = 0.110011001100 ... b/2 = ...


1

Let $1_n$ be the set of such strings of length $n$ ending in $1$. Similarly let $0_n$ be the set of such strings ending in $0$. Then we have $$ \begin{align} 1_{n+1}&=\{x\parallel 1\mid x\in 1_n\cup 0_n\}\\ 0_{n+1}&=\{x\parallel 0\mid x\in 1_n\} \end{align} $$ Define $A_n=|1_n|$ and $B_n=|0_n|$. Then we have from above $$ \begin{align} ...


0

Let $S$ be this set, and $\epsilon$ be the empty string. Define $S_0 ::= 0S_*$ and $S_* ::= \epsilon \mid 1S_0 \mid 1S_*$. $S ::= S_0 \mid S_*$. This is BNF notation. Let $u_n$ be the number of strings of length $n$ in $S_0$, and $v_n$ be the number of strings of length $n$ in $S_*$. We have $u_n = v_{n-1}$ and $v_n = u_{n-1} + v_{n-1}$. $u_0$ = 0 ...


0

First one. The xz term is redundant. You are right, your professor is wrong. $$yz + w'z + xz + wxy'$$ Expand $$yz + w'z + xz (wy + wy' + w'y + w'y') + wxy'$$ $$yz + w'z + wxyz + wxy'z + w'xyz + w'xy'z + wxy'$$ Rearrange to minimize. $$(yz + wxyz + w'xyz) + (w'z + w'xy'z) + (wxy' + wxy'z)$$ $$yz(1 + wx + w'x) + w'z (1 + xy) + wxy'(1 + z)$$ $$yz + w'z + ...


1

One intuitive approach to this problem is to let $B_n$ be the number of strings of length $n$ that contain 111, and let $A_{n,k}$ be the number of strings of length $n$ that do NOT contain 111 which end with $k$ 1's ($k=0,1,2$). Then obviously, $$B_n = 2*B_{n-1} + A_{n-1,2}$$ $$A_{n,0} = A_{n-1,0} + A_{n-1,1} + A_{n-1,2}$$ $$A_{n,1} = A_{n-1,0}$$ $$A_{n,2} ...


2

Your binary remainder is wrong. 1000111110 -------------- 10011)10101010100000 10011 ----- 100101 10011 ------ 100100 10011 ------ 100010 10011 ----- 11110 10011 ...


1

$$ \begin{align*} 10101010100000 -10011000000000&=10010100000\\ 10010100000 - 1001100000 &= 1001000000\\ 1001000000 - 100110000 &= 100010000\\ 100010000 - 10011000 &= 1111000\\ 1111000 - 1001100 &= 101100\\ 101100 - 100110 &= 110 \end{align*} $$ The remainder is 6.


0

Evidently you've made a mistake in binary division.


1

It is natural to consider (and analyze) the Collatz map not as an operation on numbers but on strings. Most obvious candidates are the strings representing the numbers in bases $2$, $3$, and $6$. In base $6$ the Collatz map is "shift invariant" and works like a cellular automaton; the reason being that $:2$ and $\times3$ are the same in base $6$; ...


1

It looks like you are doing $10_2 - 1_2 = 1_2$ Remember what the positional notation means in base $2$: Each place is twice the previous one. Expressedin base $10$, this is $2-1=1$. When you do $$\begin {align}10_2&\\ \underline{-\quad1_2}&\\ 1_2&\end {align}$$ you recognize that the $1$ in the twos place in the top line represents two in the ...



Top 50 recent answers are included