text:
# Brute-Force algorithm in C++

I wrote a brute-force algorithm which shall find all possible combinations of ASCII-values that can sum up to a specific value (int hashval).

The algorithm is derived from a recursive algorithm that could print all binary numbers that are possible within a specific length characters. I modified it, so it now iterates over all ints between first and last, thus building all combinations there are. If the sum of the combination is equal to hashval, then the combination is saved in vector<vector<int[]>> combinations. When all possible combinations are found the content of combinations is printed into a file.

I already use some little tricks I learned for competitive programming, but the algorithm is still too slow. At the moment it is running for approximately 3 hours for no more than 13 characters, with no end in sight, file I/O hasn't even started yet. I know that its Big-O for runtime is horrible, no doubt. (if I get it right it is O(m^n) ).

I considered adding a check for n=1 since that would leave only one possibility for the last character, saving some recursive calls, but that would add another if to be called in every function call, either.

What more ways are there to improve the speed? Any improvements are not bound to C++, I will take a look at every programming language which might be more efficient in this case, though I guess there scarcely will be one.

The algorithm:

#include <iostream>
#include <vector>
#include <bits/stdc++.h>
#include <cstdio>

using namespace std;
using namespace std::chrono;

//values in decimal
int first = 32, last = 126, characters = 13, hashval = 1207;

vector<vector<int>> combinations;

void brute(int n, int it, vector<int> values) {
if (n == 0) {
int sum = 0;

//sum up recent values
for (int j = 0; j < characters; ++j) {
sum += values[j];
}
//save values if matching to hash
if (sum == hashval) {
combinations.push_back(values);
}
} else {
for (int i = first; i <= last; ++i) {
values[it] = i;
brute(n - 1, it + 1, values);
}
}
}

Printing the output to a file:

void printToFile(){
freopen("fileContent.brute", "w", stdout);
cout << "\n\nFound " << combinations.size() << " combinations." << endl;
int counter = 0;
for (auto combo = combinations.begin(); combo != combinations.end(); ++combo){
for (int i = 0; i <  characters; ++i) {
cout << (char) combinations.at(counter).at(i) << " ";
}
cout<< "\r\n";
counter++;
}
}

The main-method:

int main() {
auto start = high_resolution_clock::now();
//characters = 3, first = 0, last = 3, hashval = 6;
ios_base::sync_with_stdio(false);
cin.tie(nullptr);

vector<int> values;

for (int i = 0; i < characters; ++i) {
values.push_back(first);
}

brute(characters, 0, values);

printToFile();
auto stop = high_resolution_clock::now();
auto duration = duration_cast<seconds>(stop - start);
cout << "Brute-forcing needed " << duration.count() << " seconds.\r\n";

cout.flush();

return 0;
}
• Please don't modify/add code in the question once answers have come in. If you have an improved version you want to put up for review, please wait a day or so, post it as a new question and link back to this one for bonus context. – Mast Nov 2 '19 at 1:30
• I am assuming that the theoretical model of a 4GHz machine performing a hash comparison in one clock cycle and running for 208 days straight before failing is "sufficient" as a solution? That means you need no container at all, only a uint64_t and a bitmask to clear out the uppermost bit of every byte (since ASCII is desired). That'll be a 56-bit counter to cycle through, which takes way, way long enough either way. Length is implicit (can be told from the number). – Damon Nov 2 '19 at 12:00
• Although I am volunteeringly writing this for an assignment (for which I am free to set the parameters in a way I can force the algorithm to stop in finite time), I have no real use case for the algorithm at the moment. I am looking for even better ways to do the above task for learning purposes ;) I will reask the question with the updated code some time later. – kaiya Nov 2 '19 at 15:31
• Do you actually need all possible permutations of a set of characters that sum to hashval? I mean if hashval is 65, then you would have both 32,33 and 33,32 as possible results. If you only need one of those, you can speed up your algorithm quite a lot. – <NAME> Nov 2 '19 at 17:32
• It came to my mind already some time ago that it might be more efficient to start with a string that sums up to hashval and find all the other possible solutions with +1/-1 operations in the limits of first and last character. I haven't yet figured though how that algorithm would need to look like to make sure it finally stops and doesn't run in cycles. I will try that later, though when I have time to come back to that algorithm. – kaiya Nov 3 '19 at 16:02

Here are a number of ideas that may help you improve your program.

## Don't abuse using namespace std

Putting using namespace std at the top of every program is a bad habit that you'd do well to avoid. Know when to use it and when not to (as when writing include headers). In this particular case, I happen to think it's perfectly appropriate because it's a single short program that and not a header. Some people seem to think it should never be used under any circumstance, but my view is that it can be used as long as it is done responsibly and with full knowledge of the consequences.

## Don't #include <bits/stdc++.h>

This is not a standard header and it is poor practice to include a gcc specific header in your program. See this question for elaboration on why you should not do that.

## Avoid the use of global variables

My rewrite of this code uses no global variables, so clearly they are neither faster nor necessary. Eliminating them allows your code to be more readable and maintainable, both of which are important characteristics of well-written code. Global variables introduce messy linkages that are difficult to spot and error prone.

## Use iostreams

Using both iostreams and cstdio functions is not really helpful. It's easy enough and usually cleaner to use only iostreams in modern C++ programs.

## Use constexpr where appropriate

In this program, the values of first, last, characters and hashval are never altered, so we can easily enable some compiler optimizations by declaring them all constexpr.

## Use a class

C++ is an object oriented language, and it seems natural for this problem to use an object to represent an array with the given number of characters. I implemented such a thing and the class header looks like this:

#ifndef REVERSE_HASHER2_H
#define REVERSE_HASHER2_H
#include <iostream>
#include <string>

class ReverseHasher {
public:
explicit ReverseHasher(char first, char last, char len, int hashval);
ReverseHasher& operator++();
bool isMax() const { return !more; }
friend std::ostream& operator<<(std::ostream& out, const ReverseHasher& fh);
private:
bool more{true};
const char first;
const char last;
const char characters;
std::string values;
};

#endif // REVERSE_HASHER2_H

As you can see, the constructor is given all of the relevant numbers and contains a single string of values (as per the original code) which contains the hashed string. I'll show a bit more of how this works a little later.

## Use a better algorithm

The algorithm used here is much slower than it needs to be and there are several things we could do to speed things up. First, we can check that the hash is even possible by quickly calculating the minimum and maximum values for the given character range. If the desired hash is not within that range, there are zero combinations and we're done in microseconds. Second, we can easily calculate a value that satisfies the hash value.

For instance, let's say there are $$\n = 10\$$ characters and the values range from $$\a = 0\$$ to $$\b = 9\$$ inclusive. It's easy to understand that the minimum hash value is $$\x_{\text{min}} = n * a = 10 * 0 = 0\$$ and the maximum value would be $$\x_\text{max} = n * b = 10 * 9 = 90\$$. For any hash value $$\x\$$ in that range, we could simply fill $$\\lfloor \frac{x}{b-a} \rfloor\$$ characters with $$\b\$$ and fill one character with the remainder of that division (if any) and the rest with the minimum value $$\a\$$. We can embody all of that in a constructor for the class shown above:

ReverseHasher::ReverseHasher(char first, char last, char len, int hashval) :
first{first}, last{last}, characters{len}, values(characters, first)
{
const int minval{characters * first};
const int maxval{characters * last};
const int range{last - first};
if (hashval < minval) {
throw std::domain_error("hashvalue too low; no combinations possible\n");
}
if (hashval > maxval) {
throw std::domain_error("hashvalue too high; no combinations possible\n");
}
hashval -= minval;
std::generate(values.rbegin(), values.rend(), [&hashval,first,range](){
auto digitval = std::min(hashval, range);
hashval -= digitval;
return first + digitval;
});
}

The effect is that this code either creates a sequence with the given hashval or if that's not possible, it throws an exception to indicate what's wrong.

## Increment intelligently

Rather than simply incrementing values and hoping to eventually encounter a string with the same sum, we can be a lot smarter about incrementing so that we only have valid values. Conceptually this is not hard. If we have, for instance a string of three digits, 0-9 that must sum to 11, by the previous point, we can easily come up with a valid value 029 that sums to that value. It would be nice if we increment so that the values are in numeric sequence; that is, if the values come out already sorted. So in this case, the next value would be 038. If you work through this particular example, you'll see that the next values are 047, 056, 065, 074, 083 and 092. The pattern is that we subtract one from the lowest digit and add one to the next digit. If we always subtract and add the same amounts, it's obvious we will always maintain a valid value. The algorithm is a bit tricky, but here's how it can be implemented in C++:

ReverseHasher& ReverseHasher::operator++() {
// from the right, try +1, -1 until it works
auto it{values.rbegin()};
auto end{values.rend()};
auto movable{0};
for (auto prev{it++}; it != end; ++it) {
if (*it != last && *prev != first) {
++(*it);
--(*prev);
if (movable != 0) { //propagate to the right
auto debt{movable};
while (movable && prev != values.rbegin()) {
auto delta{std::min(*prev - first, movable)};
*prev -= delta;
movable -= delta;
--prev;
}
debt -= movable;
for (auto ptr{values.rbegin()}; debt; ++ptr) {
auto delta{std::min(last - *ptr, debt)};
*ptr += delta;
debt -= delta;
}
}
return *this;
}
movable += last - *prev;
prev = it;
}
more = false;
return *this;
}

Essentially what this does it to keep trying to do the $$\+1, -1\$$ on consecutive digits, sliding to the left until it's possible to do that. But there's another step needed to make sure everything comes out in order. If we consider that the next step after 092 in the previous example would be 182 if we just did the increment in that way. That's a valid value, but in fact, the next one in sorted order would instead be 128 so we need to do a little adjustment. Essentially, as we're looking for a value to increment, each value to the right of that which isn't at the maximum value (last in the code) represents a lower value (numerically sorted). The code above keeps track of the sum of those residual values in the variable movable and then essentially redistributes that value over the next digits after the incremented one such that the largest digits are to the right and the lowest numbers are to the left, thus insuring that the terms are created in ascending order.

## Putting it all together

Here's a main function that uses this:

### main.cpp

#include <iostream>
#include <chrono>
#include "ReverseHasher2.h"

int main() {
using namespace std;
using namespace std::chrono;
auto start = high_resolution_clock::now();
ios_base::sync_with_stdio(false);
cerr.imbue(locale(""));  // get pretty local formatting for numeric values
int count{0};
for (ReverseHasher fh(32, 32+5, 13, 450); !fh.isMax(); ++fh) {
++count;
std::cout << fh << '\n';
}
auto stop = high_resolution_clock::now();
auto duration = duration_cast<milliseconds>(stop - start);
cerr << "Found " << count << " solutions in " << double(duration.count()/1000.0) << " seconds.\r\n";
}

Here's the full header file:

### ReverseHasher2.h

#ifndef REVERSE_HASHER2_H
#define REVERSE_HASHER2_H
#include <iostream>
#include <string>

class ReverseHasher {
public:
explicit ReverseHasher(char first, char last, char len, int hashval);
ReverseHasher& operator++();
bool isMax() const { return !more; }
friend std::ostream& operator<<(std::ostream& out, const ReverseHasher& fh);
private:
bool more{true};
const char first;
const char last;
const char characters;
std::string values;
};

#endif // REVERSE_HASHER2_H

And finally the full implementation of this, as mostly already listed above:

### ReverseHasher2.cpp

#include "ReverseHasher2.h"
#include <iostream>
#include <iterator>
#include <algorithm>
#include <string>

ReverseHasher::ReverseHasher(char first, char last, char len, int hashval) :
first{first}, last{last}, characters{len}, values(characters, first)
{
const int minval{characters * first};
const int maxval{characters * last};
const int range{last - first};
if (hashval < minval) {
throw std::domain_error("hashvalue too low; no combinations possible\n");
}
if (hashval > maxval) {
throw std::domain_error("hashvalue too high; no combinations possible\n");
}
hashval -= minval;
std::generate(values.rbegin(), values.rend(), [&hashval,first,range](){
auto digitval = std::min(hashval, range);
hashval -= digitval;
return first + digitval;
});
}

ReverseHasher& ReverseHasher::operator++() {
// from the right, try +1, -1 until it works
auto it{values.rbegin()};
auto end{values.rend()};
auto movable{0};
for (auto prev{it++}; it != end; ++it) {
if (*it != last && *prev != first) {
++(*it);
--(*prev);
if (movable != 0) { //propagate to the right
auto debt{movable};
while (movable && prev != values.rbegin()) {
auto delta{std::min(*prev - first, movable)};
*prev -= delta;
movable -= delta;
--prev;
}
debt -= movable;
for (auto ptr{values.rbegin()}; debt; ++ptr) {
auto delta{std::min(last - *ptr, debt)};
*ptr += delta;
debt -= delta;
}
}
return *this;
}
movable += last - *prev;
prev = it;
}
more = false;
return *this;
}

std::ostream& operator<<(std::ostream& out, const ReverseHasher& fh) {
return out << fh.values;
}

## Results

I noticed this in one of the comments:

the outcome for parameters characters = 13, last = first+5, hashval = 450 was: 9 minutes runtime

I wrote a streamlined and simplified version using the same algorithm as your original and got this result:

Found 812,525,155 solutions in 257.426 seconds.

I piped the result to /dev/null (I'm running this on a 64-bit Linux machine) because I didn't really want to waste drive space on the resulting >10GiB file. That's over 4 minutes.

With the code posted above, I got this result:

Found 812,525,155 solutions in 31.458 seconds.

In other words, it's over eight times faster.

## Going further

There are still enhancements that could be done, such as doing parallel processing, but they are not likely to buy much overall performance because the I/O is likely to be the bottleneck at this point. It's an interesting intellectual puzzle, but you probably don't really need a 10GiB file on your computer either, so it may be worth pondering in more detail what you're really trying to do, especially since this represents only a very tiny subset of the range your code was originally using. Some benchmarking and estimation of how many solutions there might be and how much space they'll require is likely to be useful in determining whether or not it's even worthwhile writing a program to do this.

• Thanks <3 I learned a lot from your answer. The question is more of curiosity and has no explicit usage at the moment. All I wanted was writing a general brute force algorithm which I can adjust for specific use cases. I will take a closer look at your code and might come back to that. I am still new to C++, so I will take this as an opportunity, too, to improve my C++ coding skills. – kaiya Nov 12 '19 at 21:55
• It was fun thinking about the problem. Thanks for asking an interesting question! – Edward Nov 12 '19 at 21:57

# Use a better container

The main issue is that std::vector<int> is a bad container for storing a set of ASCII characters. Every vector allocates on the heap, and an empty vector is likely 24 bytes in size. So this is huge waste. Why not use a container designed to hold a series of ASCII characters, like... std::string!

# Do you need to store all possible combinations in memory?

You are first building a vector of all possible combinations with the desired sum. But the only thing you are doing with it afterwards is writing the result to a file. That's a huge waste of memory, and maintaining the vector of vectors in itself costs some CPU time as well. Why not write the results to a file immediately?

# Exit early when your combination has already exceeded the desired sum

You always try to fill the vector values with characters elements, and try each possible element at each position. However, in brute(), you should calculate the partial sum of elements 0 up to n, and then just check in the for loop whether adding i to that sum would be equal to or higher than the desired sum. If so, if it's equal output the combination, but in any case return at that point instead of trying other values.

# Use \n consistently to end lines

You are mixing \n, \r\n and std::endl in your code. Stick to \n, it is the standard way of ending a line in C and C++. The underlying I/O routines will automatically convert the newlines to \r\n on Windows.

std::endl is equivalent to \n plus a call to flush(). Unless there is a good reason to, you don't want this extra flushing to happen, since it reduces the performance of your program. Normally, std::cout is line-buffered, so if something ends with a \n, it is already flushed automatically. This also means you should remove the explicit call to cout.flush().

• Adding chars isn't necessarily faster or slower than adding ints. Since you are already timing it, test it out with a smaller hashval and see if it makes any difference. Also, as a bonus, printing a std::string is trivial compared to std::vector<int> :) Furthermore, file-IO will be done buffered, so the overhead should be negligable. – G. Sliepen Nov 1 '19 at 20:21
• std::string also allocates on the heap. – Hong Ooi Nov 3 '19 at 4:40
• Further to @HongOoi 's comment, an empty std::string is likely also at least 24 bytes (unless it's the old, non-C++11-conforming Copy-On-Write std::string from GCC 4 and earlier). – Bulletmagnet Nov 3 '19 at 11:23
• @HongOoi: except that since C++11, there is the small-string optimization that avoids heap allocations. On 64-bit platforms, strings up to 22 characters avoid allocations. – G. Sliepen Nov 3 '19 at 22:42

This shouldn't be in your program:

#include <bits/stdc++.h>

You should never #include <bits/stdc++.h>. It is not even proper C++. It ruins portability and fosters terrible habits. See Why should I not #include <bits/stdc++.h>.

This is also questionable:

using namespace std;
using namespace std::chrono;

Using using directives globally is considered bad practice because it introduces name clashes and defeats the purpose of namespaces. You will encounter problems when you try to utilize an identifier as innocent as size or count.

put something like this at the beginning of your brute function and you'll see the problem pretty quick. if i had to guess this is going to take a few centuries to complete.

std::printf("brute(%d, %d, %s)\n", n, it, join(values).c_str());

ed: it's actually far worse than i imagined. on my computer it took 37.4 seconds to get one tick in the 9th cell. since you need 94 such ticks to budge the 8th cell, it will be 3520 seconds for that.

eventually you get to the 6th cell, which takes 1 year to tick. you can see now the 5th cell is going to take roughly one century.

689 billion years is a round figure to finish.

• @MelissaLoos "I know that it is inefficient, that is why I started the question": of course, but the point about calculating just how inefficient it is is well taken. It can also help you identify where and why it is inefficient. Armed with that technique, you can learn how to write more efficient algorithms more effectively. – phoog Nov 4 '19 at 17:57

Searching that way is futile, the number of candidate solutions grows exponentially with the number of characters, I would ballpark over 10^20 candidate solutions for 13 characters (an average of (95^13 / (95 * 13)) = 4.15x10^22 but it strongly depends on the value of hashval). The solutions of the equation a_1 + a_2 + ... + a_n = x form an hyperplane of dimension n - 1.

If you know that your plaintext contains only english words limit your search to these.

• I cannot limit them to english words and thus no dictionary approach seems possible. – kaiya Nov 3 '19 at 15:57
• If you don't know enough information about the plain text to limit it somehow then I don't see how you will know which of the countless candidates is the correct. – ggf31416 Nov 3 '19 at 20:23
• I got a mixed view on this. On one side, there absolutely are cases where you know how to limit the results. I already knew when writing the brute force-algorithm, that a dictionary attack would be far more efficient for the use case I was looking at. On the other side I did not want to limit my algorithm to some expected outcome, as there might be cases where I'd want to manually go over the results given by the algorithm. I see it like the comparison between RNA-seq and microarray; though you'd most commonly use the one, there are cases where you need to use the other. – kaiya Nov 12 '19 at 22:00


text:
# Solve $x^{3}-3x=\sqrt{x+2}$

Solve for real $x$

$$x^{3}-3x=\sqrt{x+2}$$

By inspection, $x=2$ is a root of this equation. So, I squared both sides and divided the six degree polynomial obtained by $x-2$. Then I got a quintic which I couldn't solve despite applying rational root theorem and substitutions. I believe that there must be some nice method to solve this which I can't think about. Please help. Thanks!

• Another root is $-\varphi$, where $\varphi$ is the golden ratio. The third belongs to the so-called irreducible case. – Lucian Jun 2 '14 at 7:01
• Are you allowed to use inspection ? As you said, once you arrived to the quintic, you are stuck ! – <NAME> Jun 2 '14 at 8:10

You shouldn't dismiss Karo's graph. Drawing a graph to get a feel for the equation (when you don't know how to proceed) is most helpful. And this isn't nonsense, in fact the graph is the key for the solution, as it makes it clear that we can consider only $x$ for which $-2 \leq x \leq 2$. This can be conveniently rewritten as $-1\leq\frac{x}{2}\leq1$.

This inequality reminds us immediately of the one that $\sin a$ and $\cos a$ also satisfy, and indeed we can assume WLOG $\frac{x}{2}=\sin a$, for some angle $a$ in radians of course. This makes $x=2 \sin a$, so let's substitute this in the equation.

\begin{align} 8\sin^3 a-6\sin a&=\sqrt{2(\sin a+1)}\\ -2(-4\sin^3a+3\sin a)&=\sqrt{2(\sin a+1)}\\ -2\sin3a&=\sqrt{2(\sin a+1)} \end{align}

It helped that we could factor it into $\sin 3a$, but then again we can't get rid of the square root in a nice way. This is because $\sin^2a$ is given in terms of $\cos 2a$, and not $\sin 2a$, so we can't turn the radicand into a nice square of a sine. On the other hand, $\cos^2 a$ can be expressed in terms of a cosine (indeed, we have the trigonometric identity $\cos^2a=\frac{1+\cos2a}{2}$). So we are lead to believe that the substituition $x=2\cos a$ is much more fortunate. It's worth a shot:

\begin{align} 8\cos^3 a-6\cos a&=\sqrt{2(\cos a+1)}\\ 2(4\cos^3a-3\cos a)&=\sqrt{4\frac{(\cos a+1)}{2}}\\ 2\cos3a&=\sqrt{2^2\cos^2\frac{a}{2}}\\ \cos3a &=\cos\frac{a}{2} \end{align}

The equation has been successfully trivialized. We should note that imposing $0\leq a\leq\pi$, $\cos a$ will still assume all of the values it possibly could, so we impose this restriction on $a$.

Therefore, we can have $3a=\frac{a}{2}\Rightarrow a=0$, which gives us the solution $x=2\cos0=2$, or we can have the other, non-trivial solutions: $$3a=\frac{a}{2}+2\pi\Rightarrow a=\frac{4\pi}{5}$$ which gives us $x=2\cos\frac{4\pi}{5}=-2\cos\frac{\pi}{5}$. If $0\leq a\leq\pi$, then $0\leq 3a \leq 3\pi\lt4\pi$, so we don't need to look the case $3a=\frac{a}{2}+4\pi$ or higher, and we just need to consider the last case: $$3a=2\pi-\frac{a}{2}\Rightarrow a=\frac{4\pi}{7}$$ Which gives us the last solution, $x=2\cos\frac{4\pi}{7}=-2\cos\frac{3\pi}{7}$.

Note: This solution was inspired by the one brazilian mathematician <NAME> presented in a lesson. Here's the link: http://y2u.be/jFFdOSsVGgg (someone who's fluent in Spanish shouldn't have trouble understanding the explanations). It is also shown that with some simple manipulations on the regular pentagon, one can arrive at $\cos\frac{\pi}{5}=\frac{1+\sqrt{5}}{4}$, so the second solution can be written as $x=-\frac{1+\sqrt{5}}{2}$ (which justifies the quadratic factor $x^2-x-1$ of the 6th degree polynomial you get when you square both sides, which obviously contains some extraneous roots).

I'm not sure there's an easy way to turn $\cos\frac{3\pi}{7}$ into one algebraic term (if there is one at all), so we just leave it that way. The solution set is $$x \in \left. \left \{ 2,-\frac{1+\sqrt{5}}{2},-2\cos\frac{3\pi}{7} \right. \right \}$$

• One could also finish the solution using the sine substituition. To get rid of the square root, write $\sin a=\cos(\frac{\pi}{2}-a)$, factor it to get rid of the square root, then transform it back into a sine. But everything goes smooth if you use cosine instead of sine. – Deathkamp Drone Jul 31 '14 at 11:09

The graph is like this and have 3 answers not one answer

• I'm sorry but the question is not about finding the number of solutions, but about solving for them. – Henry Jun 2 '14 at 7:04
• Alt solutions said that it have only one answer I just post graph that proves that it has 3 answers, I don't have enough reputations to leave comment. – Karo Jun 2 '14 at 7:09

By raising both sides to two: $$x^6-6 x^4+9 x^2-x-2 = 0,$$ (and $x^{3}-3x\geq 0$)

By decomposition you get:

$$(x-2) (x^2+x-1) (x^3+x^2-2 x-1) = 0$$

therefore you have 6 roots:

$$x=2.0$$

$$x\approx-1.618$$

$$x\approx0.618$$

$$x\approx-1.801$$

$$x\approx -0.445$$

$$x\approx 1.246$$

But you have the constraint: $x^{3}-3x\geq 0$

So, only three of the solutions are acceptable: $$x=2.0$$

$$x\approx-1.618$$ $$x\approx-0.445$$

• Can you explain the factorization? – tpb261 Jun 2 '14 at 7:00
• Actually $x\approx-1.618$ also works. And $x\approx0.445$ should be $-0.445$, which works too. – David Jun 2 '14 at 7:01
• A quick glance at the graph give 3 acceptable roots, 2 of which are less then zero. – R<NAME> Jun 2 '14 at 7:02
• @Alt How did you think about the factorization? – Henry Jun 2 '14 at 7:02
• @tpb261 The factorisation will need to be of form $(x^2+ a x \pm 1)(x^3+ b x^2+ c x+ \pm 1) = x^5+2x^4-2x^3-4x^2+x+1$, and that's not too hard to solve for integer / rational coeffts, if they exist. – Macavity Jun 2 '14 at 8:09

Let $$x+2=y^2$$ Therefore $$\sqrt{x+2}=y$$ for any positive $y$. Rewriting the whole expression in $y$, we get, $$y^6-6y^4+9y^2-y-2$$ which factorizes to $$(y-2)(y^2+y-1)(y^3+y^2-2y-1)$$ You only want the positive roots of the polynomial because $y$ can't be negative. You can easily obtain the roots of the linear, the quadratic and the cubic equation. After you've obtained the values of $y$, get the corresponding values of $x=y^2-2$. No need to solve a quintic polynomial. :)

• how is the degree 6 polynomial factorized to three factors? – tpb261 Jun 2 '14 at 7:46
• I'm sorry I don't understand your question. Are you asking me how I managed to factorize the polynomial? I just used a Computer Algebra System called maxima. Or if you're asking how a degree 6 polynomial can be factorized into 3 factors, notice that factor 1 has degree 1, factor 2 has degree 2 and factor 3 has degree 3 so they add up to 6. – sayantankhan Jun 2 '14 at 7:51
• I was asking how did you factorize the polynomial. I got the answer: " Computer Algebra System called maxima". – tpb261 Jun 2 '14 at 7:53

format: plain


text:
3 another one

Take the formula for $\cos\left(\sum_{n=0}^\infty a_n\right)$ and let all but finitely many terms be 0. Notice that you have a sum of products of sines and cosines. Each product as has only finitely many sine factors. If one of those is the sine of 0, then the whole term vanishes. But if none is the sine of 0, then you have the product of finitely many cosines of nonzero numbers and finitely infinitely factors each of which is $\cos 0 = 1$. In effect, those $\cos 0$ factors also vanish. There you have it.

....also: Look at 19th- and early 20th-century books on trigonometry. Lot's of stuff is there that you won't find in more recent books on that topic.

2 added 154 characters in body

Take the formula for $\cos\left(\sum_{n=0}^\infty a_n\right)$ and let all but finitely many terms be 0. Notice that you have a sum of products of sines and cosines. Each product as only finitely many sine factors. If one of those is the sine of 0, then the whole term vanishes. But if none is the sine of 0, then you have the product of finitely many cosines of nonzero numbers and finitely factors each of which is $\cos 0 = 1$. In effect, those $\cos 0$ factors also vanish. There you have it.

....also: Look at 19th- and early 20th-century books on trigonometry. Lot's of stuff is there that you won't find in more recent books on that topic.

1

Take the formula for $\cos\left(\sum_{n=0}^\infty a_n\right)$ and let all but finitely many terms be 0. Notice that you have a sum of products of sines and cosines. Each product as only finitely many sine factors. If one of those is the sine of 0, then the whole term vanishes. But if none is the sine of 0, then you have the product of finitely many cosines of nonzero numbers and finitely factors each of which is $\cos 0 = 1$. In effect, those $\cos 0$ factors also vanish. There you have it.


text:
# Contents

## Transition systems.

Transition systems are a well established semantic model for both sequential and concurrent systems.

###### Definition

A transition system is a structure $T = (S,i,L,Trans)$, where

• $S$ is a set of states with initial state, $i$;

• $L$ is a set of labels, sometimes referred to also as events;

• $Tran\subseteq S\times L\times S$ is the transition relation.

Let $(S, i, L, Tran )$ be a transition system. We write

$s\stackrel{a}{\to} s'$

to indicate that $(s, a, s')\in Tran$.

###### Definition

A morphism from one transition system, $T$, to another $T'$ will be a pair $(\sigma, \lambda)$, in which

• $\sigma$ is a function from the states of $T$ to those of $T'$

• $\lambda$ is a partial function from the labels of $T$ to those of $T'$ such that for any transition $s\stackrel{a}{\to} s'$ of $T$ if $\lambda(a)$ is defined, then $\sigma(s)\stackrel{\lambda(a)}{\to} \sigma(s')$ is a transition of $T'$; otherwise, if $\lambda(a)$ is undefined, then $\sigma(s) = \sigma(s')$.

It is useful to rework this definition of morphism using a variant of the idea, discussed at partial function, that replaces a partial function by a total function using the neat trick of adding an additional element $\bot$ to the codomain. (We will use the notation from partial function freely in what follows.) This is done here simply by introducing idle transitions $(s,\bot,s)$ thought of as going from $s$ to itself, and working with $L_\bot$ as a set of labels instead of $L$. (This is very neat here as it corresponds the label $\bot$ to ‘do nothing’ to the states.) After completing everything in this way we get new transition systems $T_\bot = (S,i,L_\bot, Tran_\bot)$, etc. and will work with these. (Of course, $Tran_\bot = Tran \cup \{s,\bot,s)\mid s\in S\}$.) Now a morphism $f$ is the same as given by a pair $\sigma: S\to S'$, as before, and $\lambda: L_\bot\to L'_\bot$, satisfying the compatibility condition that if $(s,a,s')\in Tran_\bot$, then $(\sigma(s),\lambda(a),\sigma(s'))\in Tran'_\bot$, (and that $\lambda_\bot(\bot) = \bot'$).

This way we get a category, $TS$, of transition systems.

The notions of transition system and of morphisms between them is clearly related to (low dimensional) cubical sets / labelled directed graphs/labelled transition systems, but we will need to consider labelled cubical sets.

## Labeled transition systems.

In the above, we have used the notation $L$ to stand for the set of events and the set of labels for those events. It is sometimes useful to make a distinction between the events themselves and their labels and to explicitly give a labelling as a function. This is important, for instance, in treating ‘relabelling’ which leads to categorical fibrational situations (see the paper by Winskel and Nielsen, cited below.) In order to make the distinction clearer, we will replace $L$ by $E$ and refer to its elements as ‘events’ in what follows.

###### Definition

A labelled transition system consists of a transition system $T = (S, i, E, Tran)$ together with a set $L$ of labels, and a function $l : E \to L$. We denote it by $(T,L,l)$.

A morphism, $(\sigma, \tau , \lambda) : (T_1 , L_1 , l_1) \to (T_2 , L_2 , l_2 )$ between labeled transition systems consists of a morphism $(\sigma, \tau) : T_1 \to T_2$ between the underlying transition systems together with a partial function $\lambda : L_1 \to L_2$ such that $l_2 \circ \tau = \lambda \circ l_1$.

We write $LTS$ for the category of labeled transition systems.

## TSs as relational structures

We can view a transition system as a relational structure. The set of states is the ‘set of worlds’ and for each event, $e \in E$ we define a relation $R_e \subseteq S\times S$ by $(s,s')\in R_e$ if and only if, $(s,e,s')\in Trans$. We thus derive a relation for each event and, conversely, if we know the family $\{R_e \mid e\in E\}$, then we can rebuild $Trans$ in the obvious way.

## Higher dimensional analogues

There are tentative definitions of

which take a more nPOV of this theory.

## References

• <NAME> and <NAME>, Models for concurrency. vol. 3, Handbook of Logic in Computer Science, pages 100 - 200, Oxford Univ. Press, 1994. (see also online technical report).

Last revised on September 8, 2012 at 13:37:00. See the history of this page for a list of all contributions to it.


text:
# Branches orientation in a tikz-tree

The folllowing code

\documentclass[border=10pt,varwidth]{standalone}
\usepackage{tikz}
\usetikzlibrary{calc, shapes, backgrounds}
\usepackage{amsmath, amssymb}
\begin{figure*}
\centering
\tikzset{
head/.style = {label = center:\textsf{\Large H}},
tail/.style = {label = center:\textsf{\Large T}}
}
\begin{tikzpicture}[
scale = 1.5, transform shape, thick,
every node/.style = {draw, circle, minimum size = 10mm},
grow = down,  % alignment of characters
level 1/.style = {sibling distance=4cm},
level 2/.style = {sibling distance=3cm},
level 3/.style = {sibling distance=2cm},
level distance = 1.25cm
]
\node[circle, draw, line width = 1pt,
minimum size = 10mm, inner sep = 0mm, font = \sffamily\large] (Start)
{root}
child { node [head] (A) {}
child { node [head] (B) {}}
child { node [tail] (C) {}}
}
child {   node [tail] (D) {}
child { node [head] (E) {}}
child { node [tail] (F) {}}
};

% Labels
\begin{scope}[nodes = {draw = none}]
\path (Start) -- (A) node [near start, left]  {$0.5$};
\path (A)     -- (B) node [near start, left]  {$0.5$};
\path (A)     -- (C) node [near start, right] {$0.5$};
\path (Start) -- (D) node [near start, right] {$0.5$};
\path (D)     -- (E) node [near start, left]  {$0.5$};
\path (D)     -- (F) node [near start, right] {$0.5$};
\end{scope}
\end{tikzpicture}
\end{figure*}

produces the output below

How coud modify the code to obtain a different orientation of the branches for some nodes? For example, as follows:

Moreover, what if I want to write different labels on different edges? For example 0.6 instead of 0.5 on the branch T-T?

## 1 Answer

with forest is relatively simple :-) :

• the first image:

\documentclass[border=10pt]{standalone}
\usepackage[edges]{forest}

\begin{document}
\begin{forest}
for tree={
circle,
draw, minimum size=8mm, font=\sffamily\Large, inner sep=1pt,
l sep = 18pt,
s sep =  6pt,
% labels on edges
EL/.style 2 args={
edge label/.wrap value={node[midway, font=\sffamily\footnotesize, #1] {#2}},
},
}, % end for tree
[root
[H,edge label=left
[H,EL={left}{0.1}
[H,EL={left}{0.3}]
[T,EL={right}{0.7}]
]
[T,EL={right}{0.9},
%calign=first
[H,EL={left}{0.6}]
[T,EL={right}{0.4}]
]
]
\end{forest}
\end{document}

• the second image:

\documentclass[border=10pt]{standalone}
\usepackage[edges]{forest}

\begin{document}
\begin{forest}
for tree={
circle,
draw, minimum size=8mm, font=\sffamily\Large, inner sep=1pt,
l sep = 18pt,
s sep =  6pt,
% labels on edges
EL/.style 2 args={
edge label/.wrap value={node[midway, font=\sffamily\footnotesize, #1] {#2}},
},
}, % end for tree
[H,EL={left}{0.1}
[H,EL={left}{0.5}]
[T,EL={right}{0.5}]
]
[T,EL={right}{0.9},
calign=first      % change branch direction
[H,EL={left}{0.5}]
[T,EL={right}{0.5}]
]
]
\end{forest}
\end{document}

edit: in both cases is now considered that each branch label can has different values.

• Thank you! But, what if I want to write different labels on different edges? For example 0.6 instead of 0.5 on the branch T-T? – Mark Jun 17 '18 at 10:22
• than you need to change code accordingly. this is not indicated in your mwe. please correct your mwe. – Zarko Jun 17 '18 at 10:46
• @Mark, see edited answer. – Zarko Jun 17 '18 at 11:00


text:
## Archive for February, 2019

### Don’t be Phased by Waveform Distortions

For many years there has been an ongoing debate about the importance of phase changes in music. Some people claim that we cannot hear the effects of phase errors, others claim that we can. Who is right? The figure below shows a waveform of a perfect fifth, with components in the ratio ${3 : 2}$ for various values of the phase-shift. Despite the different appearances, all sound pretty much the same.

Continue reading ‘Don’t be Phased by Waveform Distortions’

### Multiple Discoveries of the Thue-Morse Sequence

It is common practice in science to name important advances after the first discoverer or inventor. However, this process often goes awry. A humorous principle called Stigler’s Law holds that no scientific result is named after its original discoverer. This law was formulated by Professor <NAME> of the University of Chicago in his publication “Stigler’s law of eponymy”. He pointed out that his “law” had been proposed by others before him so it was, in a sense, self-verifying. [TM157 or search for “thatsmaths” at irishtimes.com].

Continue reading ‘Multiple Discoveries of the Thue-Morse Sequence’

### Folding Maps: A Simple but Unsolved Problem

Paper-folding is a recurring theme in mathematics. The art of origami is much-loved by many who also enjoy recreational maths. One particular folding problem is remarkably easy to state, but the solution remains elusive:

Given a map with M × N panels, how many different ways can it be folded?

Each panel is considered to be distinct, so two foldings are equivalent only when they have the same vertical sequence of the L = M × N layers.

Continue reading ‘Folding Maps: A Simple but Unsolved Problem’

### Rambling and Reckoning

A walk on the beach, in the hills or along a river bank provides great opportunities for mathematical reflection. How high is the mountain? How many grains of sand are on the beach? How much water is flowing in the river?  [TM156 or search for “thatsmaths” at irishtimes.com].

While the exact answers may be elusive, we can make reasonable guesstimates using basic knowledge and simple mathematical reasoning. And we will be walking in the footsteps of some of the world’s greatest thinkers.


text:
# Bulk Modulus of Elasticity

## Bulk Modulus of Elasticity

Bulk modulus of elasticity is one of the measures of mechanical properties of solids. Other elastic modules include Young’s modulus and Shear modulus. In any case, the bulk elastic properties of a material is used to determine how much it will compress under a given amount of external pressure.

What is a Bulk Modulus of Elasticity?

The ratio of normal stress to volume strain within elastic limit is called Bulk Modulus of Elasticity of a given material. It is denoted by K.

Suppose a force F is applied normal to a surface of a body having cross sectional area equal to A. If applied force brings about a change ΔV in the volume of the body and V is the original volume of the body then,

$$Normal\,Stress\,=\,\frac{F}{A}$$, $$Volume\,Strain\,=\,\frac{\Delta V}{V}$$.

Now, Bulk Modulus of Elasticity would be,

$$Bulk\,Modulus(K)\,=\,\frac{Normal\,Stress}{Volume\,Strain}=\frac{FV}{A\Delta V}=\frac{\Delta P}{\left( \frac{\Delta V}{V} \right)}$$.

∴ $$Bulk\,Modulus(K)=\frac{\Delta P}{\left( \frac{\Delta V}{V} \right)}$$.

Where,

ΔV = Change of the Volume of the material due to the compression,

ΔP = Change of the pressure/Force applied per unite area on the material,

V = Initial volume of the material in the units of N/ m².

For gases and liquids the normal stress is caused by change in pressure.

i.e., Normal stress = Change in pressure (ΔP).

Thus, $$Bulk\,Modulus(K)\,=\,-\frac{V\Delta P}{\Delta V}$$.

Here, negative sign indicates that the volume decreases, if pressure increases and vice versa.


text:
 <NAME> height
CYBER SALE: LOOK FOR 20-75% off THOUSANDS OF ITEMS* Start Here! How much would a lens extension tube improve the situation? //import variables Microscope magnification calculation examples: When the ocular lens is 10× and the objective lens is 10×, the field of view is 800 µm. The calculator works both online and offline. 2: An exit pupil size (diameter of light beam as it exits eyepiece) over 7.5mm might be too large for telescope designs with central obstructions (i.e. fl=250/MP; diopters=1000/fl; //write to form Description. } { Newtonian telescopes). [CDATA[ \$("#MP_input").change(function () { Here is an easy to use calculator for these questions. //calculations The calculator determines the microscope field of view from the known magnification of the objective lens and the field number of the eyepiece (ocular) lens. Greater lens magnification reduces Field of View, which calculation becomes inaccurate if magnification exceeds about 0.1 (i.e., if focus is too close, because focal length increases with close distance). Adjust the values to calculate the Magnification Difference. Description. Notes: 1: Atmospheric seeing conditions (the sky) often limits the maximum usable magnification to 250-350x. Enter the lens parameters below. Relate user supplied magnifying power to focal length and diopters of a lens. How do I calculate the power of a magnifier? Solution: The magnification at lower power is 10 × 10 = 100 The magnification at higher power is 40 × 100 = 4000 The Spectacle Magnification calculator allows you adjust certain lens parameters to change the magnification difference between the two lenses, to overcome the effects of aniseikonia. var MP,fl,diopters document.getElementById('MP_input').value = 5 } Just move the decimal point two places to the left and multiply by 2. The microscope field of view is limited by the objective lens, the diameter of the internal mechanical optical path (tube), the eyepieces used and the camera sensor size. However, other than macro lenses, normal lenses typically don't focus any closer. } Lens-Calculator. Magnifiers are only practical up to about 25x.") Relate user supplied magnifying power to focal length and diopters of a lens. Example: If the eyepiece magnification of a microscope is 10x and the objective lens in use has a magnification of 4x, calculate the magnification of the microscope. To find the magnification of your lens and extension tube combination, you simply add the extra magnification to the lens magnification. Address Book, if (MP<0 || MP>25) $$\text{FL} = \frac{250 \text{mm}}{\text{MP}}$$, $$\text{Diopters} = \frac{1000 \text{mm}}{\text{FL}}$$. Magnification Useful calculators and formulae. How to calculate the filed of view when the ocular lens is 40× and the objective lens is 100×? // ]]>. Add a stock number to begin our two-step quote process. document.getElementById('diopters_output').innerHTML = diopters.toFixed(2); So wrapping it all up - if we have a 100 mm lens with a magnification of 1, and we add a 50mm extension tube, we end up with a final magnification … Calculator assumes 250mm as the near point of the human eye, closest distance the eye can focus for comfortable vision, in order to determine basic parameters for finding the best lens for one's desired magnification. Spectacle Magnification Calculation. You can change this selection at any time, but products in your cart, saved lists, or quote may be removed if they are unavailable in the new shipping country/region. As an example, let us calculate the size of a specimen that will be recorded on the 1/2" (6.4 × 4.8 mm) camera sensor if a microscope objective lens magnification is 40 and the camera relay lens magnification is 0.35: To determine magnification, you can use a special calibration slide with engraved 0.01 mm marks (1 division equals 0.01 mm). alert("The magnifying power has to be greater than 0. Reproduction Magnification is a related property here. Contact : Catalogs : Company : Discount Programs, Copyright year, Edmund Optics Inc., 101 East Gloucester Pike, Barrington, NJ 08007-1380 USA, California Consumer Privacy Act (CCPA): Do Not Sell My Information, // .

Bin Synthetic Shellac Primer Vs Bin Shellac, Simpson College Homecoming 2019, Questrade After Hours Reddit, Gray Caulk Ace Hardware, Amati Model Ship Fittings, Corporation Tax Exemption Ireland, 2014 Nissan Pathfinder Transmission Warranty,


text:
B = transpose(A) is an alternate way to execute A.' Let X and Y be R-modules. We’ll prove that, and from that theorem we’ll automatically get corre-sponding statements for columns of matrices that we have for rows of matrices. If the matrix A describes a linear map with respect to bases of V and W, then the matrix AT describes the transpose of that linear map with respect to the dual bases. This definition also applies unchanged to left modules and to vector spaces.[9]. and enables operator overloading for classes. Here, we will learn that the determinant of the transpose is equal to the matrix itself. ', then the element B(2,3) is also 1+2i. Our mission is to provide a free, world-class education to anyone, anywhere. A symmetric matrix is a square matrix when it is equal to its transpose, defined as A=A^T. B = A.' Theorem 6. Moreover, if the diagonal entries of a diagonal matrix are all one, it is the identity matrix: Rank. Determinants and matrices, in linear algebra, are used to solve linear equations by applying Cramer’s rule to a set of non-homogeneous equations which are in linear form.Determinants are calculated for square matrices only. The determinant of a matrix is equal to the determinant of its transpose. To begin with let’s look into the role of Adjoint in finding the Inverse of a matrix and some of its theorems. Of course, probably not, but that is the reason behind those joke proofs such as 0=1 or -1=1, etc. Therefore, A is not close to being singular. Every square matrix can be represented as the product of an orthogonal matrix (representing an isometry) and an upper triangular matrix (QR decomposition)- where the determinant of an upper (or lower) triangular matrix is just the product of the elements along the diagonal (that stay in their place under transposition), so, by the Binet formula, $A=QR$ gives: \det(A^T)=\det(R^T … Back to Course. Part 5 of the matrix math series. Here, it refers to the determinant of the matrix A. Let be an square matrix: where is the jth column vector and is the ith row vector (). The entry pj i is also obtained from these rows, thus pi j = pj i, and the product matrix (pi j) is symmetric. For n ≠ m, this involves a complicated permutation of the data elements that is non-trivial to implement in-place. $\begin{bmatrix} a & b \\ c & d \end{bmatrix}$, $\begin{bmatrix} a & c \\ b & d \end{bmatrix}$, $\begin{bmatrix} a_{11} & a_{12} & a_{13} & a_{1m} \\ a_{21} & a_{22} & a_{23} & a_{2m} \\ a_{31} & a_{32} & a_{33} & a_{3m} \\ .... & .... & .... & .... \\ .... & .... & .... & .... \\ .... & .... & .... & .... \\ a_{m1} & a_{m2} & a_{m3} & a_{mm} \\ \end{bmatrix}$, $\begin{bmatrix} a_{22} & a_{23} & a_{2m} \\ a_{32} & a_{33} & a_{3m} \\ .... & .... & .... \\ .... & .... & .... \\ .... & .... & .... \\ a_{m2} & a_{m3} & a_{mm} \\ \end{bmatrix}$, $\begin{bmatrix} a_{11} & a_{21} & a_{31} & a_{m1} \\ a_{12} & a_{22} & a_{32} & a_{m2} \\ a_{13} & a_{23} & a_{33} & a_{m3} \\ .... & .... & .... & .... \\ .... & .... & .... & .... \\ .... & .... & .... & .... \\ a_{1m} & a_{2m} & a_{3m} & a_{mm} \\ \end{bmatrix}$, $\begin{bmatrix} a_{22} & a_{32} & a_{m2} \\ a_{23} & a_{33} & a_{m3} \\ .... & .... & .... \\ .... & .... & .... \\ .... & .... & .... \\ a_{2m} & a_{3m} & a_{mm} \\ \end{bmatrix}$, In the calculation of det(A), we are going to use co-factor expansion along the, Additionally, in the calculation of det(A, However, lets keep pressing on with a more 'concrete' approach (if the above logic was too abstract). If , is a square matrix. The continuous dual space of a topological vector space (TVS) X is denoted by X'. So we can then say that the determinant of A transpose is equal to this term A sub 11 times this, but this is equal to this for the n-by-n case. If, we have any given matrix A then determinant of matrix A is equal to determinant of its transpose. Up Next. Therefore, det(A) = det(), here is transpose of matrix A. In linear algebra, the transpose of a matrix is an operator which flips a matrix over its diagonal; Although the determinant of the matrix is close to zero, A is actually not ill conditioned. If , is a square matrix. does not affect the sign of the imaginary parts. So far, every-thing we’ve said about determinants of matrices was related to the rows of the matrix, so it’s some-what surprising that a matrix and its transpose have the same determinant. and enables operator overloading for classes. We can verify from example that both comes out to be equal. Correspondence <NAME> and Purdue Alumni. Every linear map to the dual space u : X → X# defines a bilinear form B : X × X → F, with the relation B(x, y) = u(x)(y). det uses the LU decomposition to calculate the determinant, which is susceptible to floating-point round-off errors. By that logic, because I have shown it to be true for the nxn case, it will then be true for the 3x3 case, 4x4 case, 5x5 case, etc...you get the idea. It calculated from the diagonal elements of a square matrix. Introduction to matrices. Determinant of a Matrix; Transpose Matrix; Here, we will learn that the determinant of the transpose is equal to the matrix itself. Linear Algebra: Determinant of Transpose Proof by induction that transposing a matrix does not change its determinant Linear Algebra: Transposes of sums and inverses. The determinant and the LU decomposition. If rows and columns are interchanged then value of determinant remains same (value does not change). Best Videos, Notes & Tests for your Most Important Exams. In this lesson we will learn about some matrix transformation techniques such as the matrix transpose, determinants and the inverse. These bilinear forms define an isomorphism between X and X#, and between Y and Y#, resulting in an isomorphism between the transpose and adjoint of u. For a 2x2 matrix, it is simply the subtraction of the product of the top left and bottom right element from the product of other two.
Messages In Romeo And Juliet, Red Snapper Taste, Creamy Strawberry Milkshake, Grow Tent Room, Kirkland Signature Country French Bread Ingredients, Blue Panda Guppy, Wilson's Storm Petrels, Anubis Symbol Tattoo, De La Cruz Sulfur Ointment Cvs, Slow Cooker Creamy Chicken Nachos,