text:
# How hard is it to find plaintexts whose hashes satisfy $h(a)\oplus h(b)=h(c)$?

Given a cryptographic hash function $h$, for example SHA256, how hard is it to find plaintexts $a,b,c$ such that $$h(a)\oplus h(b)=h(c) \text?$$

This partial answer establishes (rather trivial) lower and upper bounds for the asymptotic hardness of the problem, assuming $$h$$ behaves like an $$n$$-bit wide random function.

If one hashes $$m$$ messages $$M$$, then computes $$f(i,j,k)=h(M_i)\oplus h(M_j)\oplus h(M_k)$$ for $$(i,j,k)\in\mathbb {Z_m}^3$$, that's $$m^3$$ results, with most values duplicated at least 6 times for large $$m$$. Odds that zero is never reached by any $$f(i,j,k)$$ are about $$(1-2^{-n})^{m^3/6}$$ for large $$m$$, for any choice of the $$M$$ by an adversary who can't distinguish $$h$$ from a random function.

Therefore, if $$m\approx2^{n/3}$$ hashes have been computed, that can not lead to a solution of the problem with odds better than 16% for large parameters.

The expected hardness of the problem in the question is thus at least $$\mathcal O(2^{n/3})$$ times the work for a hash. Also, an infinitely powerful adversary could succeed with $$\mathcal O(2^{n/3})$$ queries to an oracle implementing the hash.

The above leads to an explicit algorithm with non-vanishing odds of success that performs $$(2^{n/3})^3=2^n$$ evaluations of $$f$$, thus has cost $$\mathcal O(2^n)$$ $$n$$-bit operations; it requires $$\mathcal O(2^{n/3})$$ $$n$$-bit words of memory. We can do much better.

One option is to fix $$a$$, then find collisions for the function $$g(x)=\begin{cases}h(x) & \text{if }x\text{ is even}\\h(x)\oplus h(a) & \text{if }x\text{ is odd}\end{cases}$$ This search can be can be made with cost $$\mathcal O(2^{n/2})$$ hashes and modest memory, using Floyd's cycle-finding, or Paul C. van Oorschot and Michael J. Wiener's Parallel Collision Search with Cryptanalytic Applications (in Journal of Cryptology, January 1999, Volume 12, Issue 1; free slightly earlier version available from the first author's website).

Notice that if $$g(b)=g(c)$$ with $$b\ne c$$, then $$(a,b,c)$$ is a solution of the problem of the question if $$b$$ and $$c$$ have different parity, which (for random $$h$$) has odds about $$1/2$$ for each collision exhibited.

The expected hardness of the problem in the question is thus at most $$\mathcal O(2^{n/2})$$ times the work for a hash.

• And it's easy to show that it's at most $O(2^{n/2})$ -- how can we establish where in that range the answer is? – poncho Jan 30 '15 at 18:51
• @Poncho: Did you think to Birthday attack when you claim $O(2^{n/2})$ ? – Robert NACIRI Jan 30 '15 at 22:36
• Not true for all cryptographic hash functions, there are cryptographically strong hash functions for which generating triples of this form are downright trivial. notably SWIFFT where f(a + b) = f(a) + f(b) your answer is valid for cryptographic hashes that are also psuedorandom though, because if there were an easier than brute force way to generate the triples it would distinguish the function from a random function. – John Meacham Jan 31 '15 at 2:01
• @JohnMeacham, I'm not familiar with SWIFFT, but if it satisfies $f(a+b)=f(a)+f(b)$, I would not call it a cryptographic hash function. The question specifically asks about cryptographic hash functions (and mentions SHA256 as an example); the term "cryptographic hash function" is often understood to require that the hash is effectively pseudorandom. So I think your criticism is debatable. If you have questions about what the OP meant by "cryptographic hash function", I suggest posting a comment underneath the question to ask the original poster to clarify. – D.W. Feb 1 '15 at 20:13
• @Hyperflame: Ah, I now see what you mean. I have changed the answer to clarify that I meant cost in units of work for a hash, and added discussion of number of (queries to an oracle implementing the) hash for an infinitely powerful adversary. – fgrieu Feb 7 '15 at 14:49

This is basically something that is called a 3-XOR problem, and was studied for some time.

In short, the best known time complexity is $$2^{n/2}$$ for $$n$$-bit hash. However, naive approach requires lots of memory, and there are methods to reduce the memory complexity (sometimes at the cost of more time).

For details see recent work [1], slides are also available.

Note: Current record for SHA256 is a 3-XOR with 119 zero bits, made using mass computations ;) See [2] to have some fun.

[1] Bouillaguet et al. (TOSC 2018 (1)) Revisiting and Improving Algorithms for the 3XOR Problem.

[2] Gaëtan Leurent. Cryptanalysis Records. FSE 2018 Rump Session Slides, p.160. https://fse.iacr.org/2018/files/proceedings_rumpsession.pdf


text:
:: Isometric Differentiable Functions on Real Normed Space
:: by Yuichi Futa , Noboru Endou and Yasunari Shidama
::
:: Copyright (c) 2013-2021 Association of Mizar Users

reconsider jj = 1 as Element of REAL by XREAL_0:def 1;

theorem FX1: :: NDIFF_7:1
for X being set
for I, f being Function holds (f | X) * I = (f * I) | (I " X)
proof end;

theorem LM001: :: NDIFF_7:2
for S, T being RealNormSpace
for L being LinearOperator of S,T
for x, y being Point of S holds (L . x) - (L . y) = L . (x - y)
proof end;

theorem Th26: :: NDIFF_7:3
for X, Y, W being RealNormSpace
for I being Function of X,Y
for f1, f2 being PartFunc of Y,W holds
( (f1 + f2) * I = (f1 * I) + (f2 * I) & (f1 - f2) * I = (f1 * I) - (f2 * I) )
proof end;

theorem Th27: :: NDIFF_7:4
for X, Y, W being RealNormSpace
for I being Function of X,Y
for f being PartFunc of Y,W
for r being Real holds r (#) (f * I) = (r (#) f) * I
proof end;

theorem LM030: :: NDIFF_7:5
for S, T, W being RealNormSpace
for f being PartFunc of T,W
for g being Function of S,T
for x being Point of S st x in dom g & g /. x in dom f & g is_continuous_in x & f is_continuous_in g /. x holds
f * g is_continuous_in x
proof end;

definition
let X, Y be RealNormSpace;
let x be Element of [:X,Y:];
func reproj1 x -> Function of X,[:X,Y:] means :Defrep1: :: NDIFF_7:def 1
for r being Element of X holds it . r = [r,(x 2)];
existence
ex b1 being Function of X,[:X,Y:] st
for r being Element of X holds b1 . r = [r,(x 2)]
proof end;
uniqueness
for b1, b2 being Function of X,[:X,Y:] st ( for r being Element of X holds b1 . r = [r,(x 2)] ) & ( for r being Element of X holds b2 . r = [r,(x 2)] ) holds
b1 = b2
proof end;
func reproj2 x -> Function of Y,[:X,Y:] means :Defrep2: :: NDIFF_7:def 2
for r being Element of Y holds it . r = [(x 1),r];
existence
ex b1 being Function of Y,[:X,Y:] st
for r being Element of Y holds b1 . r = [(x 1),r]
proof end;
uniqueness
for b1, b2 being Function of Y,[:X,Y:] st ( for r being Element of Y holds b1 . r = [(x 1),r] ) & ( for r being Element of Y holds b2 . r = [(x 1),r] ) holds
b1 = b2
proof end;
end;

:: deftheorem Defrep1 defines reproj1 NDIFF_7:def 1 :
for X, Y being RealNormSpace
for x being Element of [:X,Y:]
for b4 being Function of X,[:X,Y:] holds
( b4 = reproj1 x iff for r being Element of X holds b4 . r = [r,(x 2)] );

:: deftheorem Defrep2 defines reproj2 NDIFF_7:def 2 :
for X, Y being RealNormSpace
for x being Element of [:X,Y:]
for b4 being Function of Y,[:X,Y:] holds
( b4 = reproj2 x iff for r being Element of Y holds b4 . r = [(x 1),r] );

theorem LM010: :: NDIFF_7:6
for S, T being RealNormSpace
for I being LinearOperator of S,T
for x being Point of S st I is isometric holds
I is_continuous_in x
proof end;

theorem LMMAZU: :: NDIFF_7:7
for S, T being RealNormSpace
for f being LinearOperator of S,T holds
( f is isometric iff for x being Element of S holds ||.(f . x).|| = )
proof end;

theorem LM015: :: NDIFF_7:8
for S, T being RealNormSpace
for I being LinearOperator of S,T
for Z being Subset of S st I is isometric holds
I is_continuous_on Z
proof end;

theorem LM020: :: NDIFF_7:9
for S, T being RealNormSpace
for I being LinearOperator of S,T st I is one-to-one & I is onto & I is isometric holds
ex J being LinearOperator of T,S st
( J = I " & J is one-to-one & J is onto & J is isometric )
proof end;

theorem LM021: :: NDIFF_7:10
for S, T being RealNormSpace
for I being LinearOperator of S,T
for s1 being sequence of S st I is isometric & s1 is convergent holds
( I * s1 is convergent & lim (I * s1) = I . (lim s1) )
proof end;

theorem LM022: :: NDIFF_7:11
for S, T being RealNormSpace
for I being LinearOperator of S,T
for s1 being sequence of S st I is one-to-one & I is onto & I is isometric holds
( s1 is convergent iff I * s1 is convergent )
proof end;

LM023: for S, T being RealNormSpace
for I being LinearOperator of S,T
for Z being Subset of S st I is one-to-one & I is onto & I is isometric & Z is closed holds
I .: Z is closed

proof end;

theorem LM024: :: NDIFF_7:12
for S, T being RealNormSpace
for I being LinearOperator of S,T
for Z being Subset of S st I is one-to-one & I is onto & I is isometric holds
( Z is closed iff I .: Z is closed )
proof end;

theorem LM025: :: NDIFF_7:13
for S, T being RealNormSpace
for I being LinearOperator of S,T
for Z being Subset of S st I is one-to-one & I is onto & I is isometric holds
( Z is open iff I .: Z is open )
proof end;

LM026: for S, T being RealNormSpace
for I being LinearOperator of S,T
for Z being Subset of S st I is isometric & Z is compact holds
I .: Z is compact

proof end;

theorem :: NDIFF_7:14
for S, T being RealNormSpace
for I being LinearOperator of S,T
for Z being Subset of S st I is one-to-one & I is onto & I is isometric holds
( Z is compact iff I .: Z is compact )
proof end;

theorem LM040: :: NDIFF_7:15
for S, T, W being RealNormSpace
for f being PartFunc of T,W
for I being LinearOperator of S,T st I is one-to-one & I is onto & I is isometric holds
for x being Point of S st I . x in dom f holds
( f * I is_continuous_in x iff f is_continuous_in I . x )
proof end;

theorem LM045: :: NDIFF_7:16
for S, T, W being RealNormSpace
for f being PartFunc of T,W
for I being LinearOperator of S,T
for X being set st X c= the carrier of T & I is one-to-one & I is onto & I is isometric holds
( f is_continuous_on X iff f * I is_continuous_on I " X )
proof end;

definition
let X, Y be RealNormSpace;
func IsoCPNrSP (X,Y) -> LinearOperator of [:X,Y:],(product <*X,Y*>) means :defISO: :: NDIFF_7:def 3
for x being Point of X
for y being Point of Y holds it . (x,y) = <*x,y*>;
existence
ex b1 being LinearOperator of [:X,Y:],(product <*X,Y*>) st
for x being Point of X
for y being Point of Y holds b1 . (x,y) = <*x,y*>
proof end;
uniqueness
for b1, b2 being LinearOperator of [:X,Y:],(product <*X,Y*>) st ( for x being Point of X
for y being Point of Y holds b1 . (x,y) = <*x,y*> ) & ( for x being Point of X
for y being Point of Y holds b2 . (x,y) = <*x,y*> ) holds
b1 = b2
proof end;
end;

:: deftheorem defISO defines IsoCPNrSP NDIFF_7:def 3 :
for X, Y being RealNormSpace
for b3 being LinearOperator of [:X,Y:],(product <*X,Y*>) holds
( b3 = IsoCPNrSP (X,Y) iff for x being Point of X
for y being Point of Y holds b3 . (x,y) = <*x,y*> );

theorem ZeZe: :: NDIFF_7:17
for X, Y being RealNormSpace holds 0. (product <*X,Y*>) = (IsoCPNrSP (X,Y)) . (0. [:X,Y:])
proof end;

registration
let X, Y be RealNormSpace;
correctness
coherence
( IsoCPNrSP (X,Y) is one-to-one & IsoCPNrSP (X,Y) is onto & IsoCPNrSP (X,Y) is isometric )
;
proof end;
end;

registration
let X, Y be RealNormSpace;
cluster Relation-like the carrier of [:X,Y:] -defined the carrier of (product <*X,Y*>) -valued non empty Function-like one-to-one total quasi_total onto V152([:X,Y:], product <*X,Y*>) V153([:X,Y:], product <*X,Y*>) isometric for Element of bool [: the carrier of [:X,Y:], the carrier of (product <*X,Y*>):];
correctness
existence
ex b1 being LinearOperator of [:X,Y:],(product <*X,Y*>) st
( b1 is one-to-one & b1 is onto & b1 is isometric )
;
proof end;
end;

definition
let X, Y be RealNormSpace;
let f be one-to-one onto isometric LinearOperator of [:X,Y:],(product <*X,Y*>);
:: original: "
redefine func f " -> LinearOperator of (product <*X,Y*>),[:X,Y:];
correctness
coherence
f " is LinearOperator of (product <*X,Y*>),[:X,Y:]
;
proof end;
end;

registration
let X, Y be RealNormSpace;
let f be one-to-one onto isometric LinearOperator of [:X,Y:],(product <*X,Y*>);
cluster f " -> one-to-one onto isometric for LinearOperator of (product <*X,Y*>),[:X,Y:];
correctness
coherence
for b1 being LinearOperator of (product <*X,Y*>),[:X,Y:] st b1 = f " holds
( b1 is one-to-one & b1 is onto & b1 is isometric )
;
proof end;
end;

registration
let X, Y be RealNormSpace;
cluster Relation-like the carrier of (product <*X,Y*>) -defined the carrier of [:X,Y:] -valued non empty Function-like one-to-one total quasi_total onto V152( product <*X,Y*>,[:X,Y:]) V153( product <*X,Y*>,[:X,Y:]) isometric for Element of bool [: the carrier of (product <*X,Y*>), the carrier of [:X,Y:]:];
correctness
existence
ex b1 being LinearOperator of (product <*X,Y*>),[:X,Y:] st
( b1 is one-to-one & b1 is onto & b1 is isometric )
;
proof end;
end;

theorem defISOA1: :: NDIFF_7:18
for X, Y being RealNormSpace
for x being Point of X
for y being Point of Y holds ((IsoCPNrSP (X,Y)) ") . <*x,y*> = [x,y]
proof end;

theorem defISOA2: :: NDIFF_7:19
for X, Y being RealNormSpace holds ((IsoCPNrSP (X,Y)) ") . (0. (product <*X,Y*>)) = 0. [:X,Y:]
proof end;

theorem :: NDIFF_7:20
for X, Y being RealNormSpace
for Z being Subset of [:X,Y:] holds IsoCPNrSP (X,Y) is_continuous_on Z by LM015;

theorem :: NDIFF_7:21
for X, Y being RealNormSpace
for Z being Subset of (product <*X,Y*>) holds (IsoCPNrSP (X,Y)) " is_continuous_on Z by LM015;

theorem LMX00: :: NDIFF_7:22
for S, T, W being RealNormSpace
for f being Point of
for g being Point of
for I being LinearOperator of S,T st I is one-to-one & I is onto & I is isometric & f = g * I holds
=
proof end;

registration
let S, T be RealNormSpace;
cluster Function-like quasi_total V152(S,T) V153(S,T) isometric -> Lipschitzian for Element of bool [: the carrier of S, the carrier of T:];
coherence
for b1 being LinearOperator of S,T st b1 is isometric holds
b1 is Lipschitzian
proof end;
end;

theorem :: NDIFF_7:23
for G being RealNormSpace-Sequence
for F being RealNormSpace
for i being set
for f, g being PartFunc of (),F
for X being Subset of () st X is open & i in dom G & f is_partial_differentiable_on X,i & g is_partial_differentiable_on X,i holds
( f + g is_partial_differentiable_on X,i & (f + g) partial| (X,i) = (f partial| (X,i)) + (g partial| (X,i)) )
proof end;

theorem :: NDIFF_7:24
for G being RealNormSpace-Sequence
for F being RealNormSpace
for i being set
for f, g being PartFunc of (),F
for X being Subset of () st X is open & i in dom G & f is_partial_differentiable_on X,i & g is_partial_differentiable_on X,i holds
( f - g is_partial_differentiable_on X,i & (f - g) partial| (X,i) = (f partial| (X,i)) - (g partial| (X,i)) )
proof end;

theorem :: NDIFF_7:25
for G being RealNormSpace-Sequence
for F being RealNormSpace
for i being set
for f being PartFunc of (),F
for r being Real
for X being Subset of () st X is open & i in dom G & f is_partial_differentiable_on X,i holds
( r (#) f is_partial_differentiable_on X,i & (r (#) f) partial| (X,i) = r (#) (f partial| (X,i)) )
proof end;

theorem LM090: :: NDIFF_7:26
for S, T being RealNormSpace
for L being Lipschitzian LinearOperator of S,T
for x0 being Point of S holds
( L is_differentiable_in x0 & diff (L,x0) = L )
proof end;

theorem LM120: :: NDIFF_7:27
for S, T, W being RealNormSpace
for f being PartFunc of T,W
for I being Lipschitzian LinearOperator of S,T
for I0 being Point of st I0 = I holds
for x being Point of S st f is_differentiable_in I . x holds
( f * I is_differentiable_in x & diff ((f * I),x) = (diff (f,(I . x))) * I0 )
proof end;

theorem LM150: :: NDIFF_7:28
for S, T, W being RealNormSpace
for f being PartFunc of T,W
for I being LinearOperator of S,T st I is one-to-one & I is onto & I is isometric holds
for x being Point of S holds
( f * I is_differentiable_in x iff f is_differentiable_in I . x )
proof end;

theorem LM155: :: NDIFF_7:29
for S, T, W being RealNormSpace
for f being PartFunc of T,W
for I being LinearOperator of S,T
for X being set st X c= the carrier of T & I is one-to-one & I is onto & I is isometric holds
( f is_differentiable_on X iff f * I is_differentiable_on I " X )
proof end;

theorem :: NDIFF_7:30
for W, X, Y being RealNormSpace
for f being PartFunc of (product <*X,Y*>),W
for D being Subset of (product <*X,Y*>) st f is_differentiable_on D holds
for z being Point of (product <*X,Y*>) st z in dom (f | D) holds
(f | D) . z = (((f * (IsoCPNrSP (X,Y))) | ((IsoCPNrSP (X,Y)) " D)) /. (((IsoCPNrSP (X,Y)) ") . z)) * ((IsoCPNrSP (X,Y)) ")
proof end;

theorem LM166: :: NDIFF_7:31
for W, X, Y being RealNormSpace
for f being PartFunc of [:X,Y:],W
for D being Subset of [:X,Y:] st f is_differentiable_on D holds
for z being Point of [:X,Y:] st z in dom (f | D) holds
(f | D) . z = (((f * ((IsoCPNrSP (X,Y)) ")) | (((IsoCPNrSP (X,Y)) ") " D)) /. ((IsoCPNrSP (X,Y)) . z)) * (((IsoCPNrSP (X,Y)) ") ")
proof end;

theorem LM180: :: NDIFF_7:32
for X, Y being RealNormSpace
for z being Point of [:X,Y:] holds
( reproj1 z = ((IsoCPNrSP (X,Y)) ") * (reproj ((In (1,(dom <*X,Y*>))),((IsoCPNrSP (X,Y)) . z))) & reproj2 z = ((IsoCPNrSP (X,Y)) ") * (reproj ((In (2,(dom <*X,Y*>))),((IsoCPNrSP (X,Y)) . z))) )
proof end;

definition
let X, Y be RealNormSpace;
let z be Point of [:X,Y:];
:: original: 1
redefine func z 1 -> Point of X;
correctness
coherence
z 1 is Point of X
;
proof end;
:: original: 2
redefine func z 2 -> Point of Y;
correctness
coherence
z 2 is Point of Y
;
proof end;
end;

definition
let X, Y, W be RealNormSpace;
let z be Point of [:X,Y:];
let f be PartFunc of [:X,Y:],W;
end;

:: deftheorem defines is_partial_differentiable_in1 NDIFF_7:def 4 :
for X, Y, W being RealNormSpace
for z being Point of [:X,Y:]
for f being PartFunc of [:X,Y:],W holds
( f is_partial_differentiable_in1 z iff f * () is_differentiable_in z 1 );

:: deftheorem defines is_partial_differentiable_in2 NDIFF_7:def 5 :
for X, Y, W being RealNormSpace
for z being Point of [:X,Y:]
for f being PartFunc of [:X,Y:],W holds
( f is_partial_differentiable_in2 z iff f * () is_differentiable_in z 2 );

theorem LM190: :: NDIFF_7:33
for X, Y being RealNormSpace
for z being Point of [:X,Y:] holds
( z 1 = (proj (In (1,(dom <*X,Y*>)))) . ((IsoCPNrSP (X,Y)) . z) & z 2 = (proj (In (2,(dom <*X,Y*>)))) . ((IsoCPNrSP (X,Y)) . z) )
proof end;

theorem LM200: :: NDIFF_7:34
for X, Y, W being RealNormSpace
for z being Point of [:X,Y:]
for f being PartFunc of [:X,Y:],W holds
( ( f is_partial_differentiable_in1 z implies f * ((IsoCPNrSP (X,Y)) ") is_partial_differentiable_in (IsoCPNrSP (X,Y)) . z,1 ) & ( f * ((IsoCPNrSP (X,Y)) ") is_partial_differentiable_in (IsoCPNrSP (X,Y)) . z,1 implies f is_partial_differentiable_in1 z ) & ( f is_partial_differentiable_in2 z implies f * ((IsoCPNrSP (X,Y)) ") is_partial_differentiable_in (IsoCPNrSP (X,Y)) . z,2 ) & ( f * ((IsoCPNrSP (X,Y)) ") is_partial_differentiable_in (IsoCPNrSP (X,Y)) . z,2 implies f is_partial_differentiable_in2 z ) )
proof end;

definition
let X, Y, W be RealNormSpace;
let z be Point of [:X,Y:];
let f be PartFunc of [:X,Y:],W;
func partdiff1 (f,z) -> Point of equals :: NDIFF_7:def 6
diff ((f * ()),(z 1));
coherence
diff ((f * ()),(z 1)) is Point of
;
func partdiff2 (f,z) -> Point of equals :: NDIFF_7:def 7
diff ((f * ()),(z 2));
coherence
diff ((f * ()),(z 2)) is Point of
;
end;

:: deftheorem defines partdiff1 NDIFF_7:def 6 :
for X, Y, W being RealNormSpace
for z being Point of [:X,Y:]
for f being PartFunc of [:X,Y:],W holds partdiff1 (f,z) = diff ((f * ()),(z 1));

:: deftheorem defines partdiff2 NDIFF_7:def 7 :
for X, Y, W being RealNormSpace
for z being Point of [:X,Y:]
for f being PartFunc of [:X,Y:],W holds partdiff2 (f,z) = diff ((f * ()),(z 2));

theorem LM210: :: NDIFF_7:35
for X, Y, W being RealNormSpace
for z being Point of [:X,Y:]
for f being PartFunc of [:X,Y:],W holds
( partdiff1 (f,z) = partdiff ((f * ((IsoCPNrSP (X,Y)) ")),((IsoCPNrSP (X,Y)) . z),1) & partdiff2 (f,z) = partdiff ((f * ((IsoCPNrSP (X,Y)) ")),((IsoCPNrSP (X,Y)) . z),2) )
proof end;

theorem LM215: :: NDIFF_7:36
for X, Y, W being RealNormSpace
for z being Point of [:X,Y:]
for f1, f2 being PartFunc of [:X,Y:],W st f1 is_partial_differentiable_in1 z & f2 is_partial_differentiable_in1 z holds
( f1 + f2 is_partial_differentiable_in1 z & partdiff1 ((f1 + f2),z) = (partdiff1 (f1,z)) + (partdiff1 (f2,z)) & f1 - f2 is_partial_differentiable_in1 z & partdiff1 ((f1 - f2),z) = (partdiff1 (f1,z)) - (partdiff1 (f2,z)) )
proof end;

theorem LM216: :: NDIFF_7:37
for X, Y, W being RealNormSpace
for z being Point of [:X,Y:]
for f1, f2 being PartFunc of [:X,Y:],W st f1 is_partial_differentiable_in2 z & f2 is_partial_differentiable_in2 z holds
( f1 + f2 is_partial_differentiable_in2 z & partdiff2 ((f1 + f2),z) = (partdiff2 (f1,z)) + (partdiff2 (f2,z)) & f1 - f2 is_partial_differentiable_in2 z & partdiff2 ((f1 - f2),z) = (partdiff2 (f1,z)) - (partdiff2 (f2,z)) )
proof end;

theorem LM217: :: NDIFF_7:38
for X, Y, W being RealNormSpace
for z being Point of [:X,Y:]
for r being Real
for f being PartFunc of [:X,Y:],W st f is_partial_differentiable_in1 z holds
( r (#) f is_partial_differentiable_in1 z & partdiff1 ((r (#) f),z) = r * (partdiff1 (f,z)) )
proof end;

theorem LM218: :: NDIFF_7:39
for X, Y, W being RealNormSpace
for z being Point of [:X,Y:]
for r being Real
for f being PartFunc of [:X,Y:],W st f is_partial_differentiable_in2 z holds
( r (#) f is_partial_differentiable_in2 z & partdiff2 ((r (#) f),z) = r * (partdiff2 (f,z)) )
proof end;

definition
let X, Y, W be RealNormSpace;
let Z be set ;
let f be PartFunc of [:X,Y:],W;
pred f is_partial_differentiable_on1 Z means :: NDIFF_7:def 8
( Z c= dom f & ( for z being Point of [:X,Y:] st z in Z holds
f | Z is_partial_differentiable_in1 z ) );
pred f is_partial_differentiable_on2 Z means :: NDIFF_7:def 9
( Z c= dom f & ( for z being Point of [:X,Y:] st z in Z holds
f | Z is_partial_differentiable_in2 z ) );
end;

:: deftheorem defines is_partial_differentiable_on1 NDIFF_7:def 8 :
for X, Y, W being RealNormSpace
for Z being set
for f being PartFunc of [:X,Y:],W holds
( f is_partial_differentiable_on1 Z iff ( Z c= dom f & ( for z being Point of [:X,Y:] st z in Z holds
f | Z is_partial_differentiable_in1 z ) ) );

:: deftheorem defines is_partial_differentiable_on2 NDIFF_7:def 9 :
for X, Y, W being RealNormSpace
for Z being set
for f being PartFunc of [:X,Y:],W holds
( f is_partial_differentiable_on2 Z iff ( Z c= dom f & ( for z being Point of [:X,Y:] st z in Z holds
f | Z is_partial_differentiable_in2 z ) ) );

theorem LM300: :: NDIFF_7:40
for X, Y, W being RealNormSpace
for Z being Subset of [:X,Y:]
for f being PartFunc of [:X,Y:],W holds
( ( f is_partial_differentiable_on1 Z implies f * ((IsoCPNrSP (X,Y)) ") is_partial_differentiable_on ((IsoCPNrSP (X,Y)) ") " Z,1 ) & ( f * ((IsoCPNrSP (X,Y)) ") is_partial_differentiable_on ((IsoCPNrSP (X,Y)) ") " Z,1 implies f is_partial_differentiable_on1 Z ) & ( f is_partial_differentiable_on2 Z implies f * ((IsoCPNrSP (X,Y)) ") is_partial_differentiable_on ((IsoCPNrSP (X,Y)) ") " Z,2 ) & ( f * ((IsoCPNrSP (X,Y)) ") is_partial_differentiable_on ((IsoCPNrSP (X,Y)) ") " Z,2 implies f is_partial_differentiable_on2 Z ) )
proof end;

definition
let X, Y, W be RealNormSpace;
let Z be set ;
let f be PartFunc of [:X,Y:],W;
assume A2: f is_partial_differentiable_on1 Z ;
func f partial1| Z -> PartFunc of [:X,Y:], means :Def91: :: NDIFF_7:def 10
( dom it = Z & ( for z being Point of [:X,Y:] st z in Z holds
it /. z = partdiff1 (f,z) ) );
existence
ex b1 being PartFunc of [:X,Y:], st
( dom b1 = Z & ( for z being Point of [:X,Y:] st z in Z holds
b1 /. z = partdiff1 (f,z) ) )
proof end;
uniqueness
for b1, b2 being PartFunc of [:X,Y:], st dom b1 = Z & ( for z being Point of [:X,Y:] st z in Z holds
b1 /. z = partdiff1 (f,z) ) & dom b2 = Z & ( for z being Point of [:X,Y:] st z in Z holds
b2 /. z = partdiff1 (f,z) ) holds
b1 = b2
proof end;
end;

:: deftheorem Def91 defines partial1| NDIFF_7:def 10 :
for X, Y, W being RealNormSpace
for Z being set
for f being PartFunc of [:X,Y:],W st f is_partial_differentiable_on1 Z holds
for b6 being PartFunc of [:X,Y:], holds
( b6 = f partial1| Z iff ( dom b6 = Z & ( for z being Point of [:X,Y:] st z in Z holds
b6 /. z = partdiff1 (f,z) ) ) );

definition
let X, Y, W be RealNormSpace;
let Z be set ;
let f be PartFunc of [:X,Y:],W;
assume A2: f is_partial_differentiable_on2 Z ;
func f partial2| Z -> PartFunc of [:X,Y:], means :Def92: :: NDIFF_7:def 11
( dom it = Z & ( for z being Point of [:X,Y:] st z in Z holds
it /. z = partdiff2 (f,z) ) );
existence
ex b1 being PartFunc of [:X,Y:], st
( dom b1 = Z & ( for z being Point of [:X,Y:] st z in Z holds
b1 /. z = partdiff2 (f,z) ) )
proof end;
uniqueness
for b1, b2 being PartFunc of [:X,Y:], st dom b1 = Z & ( for z being Point of [:X,Y:] st z in Z holds
b1 /. z = partdiff2 (f,z) ) & dom b2 = Z & ( for z being Point of [:X,Y:] st z in Z holds
b2 /. z = partdiff2 (f,z) ) holds
b1 = b2
proof end;
end;

:: deftheorem Def92 defines partial2| NDIFF_7:def 11 :
for X, Y, W being RealNormSpace
for Z being set
for f being PartFunc of [:X,Y:],W st f is_partial_differentiable_on2 Z holds
for b6 being PartFunc of [:X,Y:], holds
( b6 = f partial2| Z iff ( dom b6 = Z & ( for z being Point of [:X,Y:] st z in Z holds
b6 /. z = partdiff2 (f,z) ) ) );

theorem LM400: :: NDIFF_7:41
for X, Y, W being RealNormSpace
for Z being Subset of [:X,Y:]
for f being PartFunc of [:X,Y:],W st f is_partial_differentiable_on1 Z holds
f partial1| Z = ((f * ((IsoCPNrSP (X,Y)) ")) partial| ((((IsoCPNrSP (X,Y)) ") " Z),1)) * (IsoCPNrSP (X,Y))
proof end;

theorem LM401: :: NDIFF_7:42
for X, Y, W being RealNormSpace
for Z being Subset of [:X,Y:]
for f being PartFunc of [:X,Y:],W st f is_partial_differentiable_on2 Z holds
f partial2| Z = ((f * ((IsoCPNrSP (X,Y)) ")) partial| ((((IsoCPNrSP (X,Y)) ") " Z),2)) * (IsoCPNrSP (X,Y))
proof end;

theorem NDIFF5241: :: NDIFF_7:43
for X, Y, W being RealNormSpace
for Z being Subset of [:X,Y:]
for f being PartFunc of [:X,Y:],W st Z is open holds
( f is_partial_differentiable_on1 Z iff ( Z c= dom f & ( for x being Point of [:X,Y:] st x in Z holds
f is_partial_differentiable_in1 x ) ) )
proof end;

theorem NDIFF5242: :: NDIFF_7:44
for X, Y, W being RealNormSpace
for Z being Subset of [:X,Y:]
for f being PartFunc of [:X,Y:],W st Z is open holds
( f is_partial_differentiable_on2 Z iff ( Z c= dom f & ( for x being Point of [:X,Y:] st x in Z holds
f is_partial_differentiable_in2 x ) ) )
proof end;

theorem :: NDIFF_7:45
for X, Y, W being RealNormSpace
for Z being Subset of [:X,Y:]
for f, g being PartFunc of [:X,Y:],W st Z is open & f is_partial_differentiable_on1 Z & g is_partial_differentiable_on1 Z holds
( f + g is_partial_differentiable_on1 Z & (f + g) partial1| Z = () + () )
proof end;

theorem :: NDIFF_7:46
for X, Y, W being RealNormSpace
for Z being Subset of [:X,Y:]
for f, g being PartFunc of [:X,Y:],W st Z is open & f is_partial_differentiable_on1 Z & g is_partial_differentiable_on1 Z holds
( f - g is_partial_differentiable_on1 Z & (f - g) partial1| Z = () - () )
proof end;

theorem :: NDIFF_7:47
for X, Y, W being RealNormSpace
for Z being Subset of [:X,Y:]
for f, g being PartFunc of [:X,Y:],W st Z is open & f is_partial_differentiable_on2 Z & g is_partial_differentiable_on2 Z holds
( f + g is_partial_differentiable_on2 Z & (f + g) partial2| Z = () + () )
proof end;

theorem :: NDIFF_7:48
for X, Y, W being RealNormSpace
for Z being Subset of [:X,Y:]
for f, g being PartFunc of [:X,Y:],W st Z is open & f is_partial_differentiable_on2 Z & g is_partial_differentiable_on2 Z holds
( f - g is_partial_differentiable_on2 Z & (f - g) partial2| Z = () - () )
proof end;

theorem :: NDIFF_7:49
for X, Y, W being RealNormSpace
for Z being Subset of [:X,Y:]
for r being Real
for f being PartFunc of [:X,Y:],W st Z is open & f is_partial_differentiable_on1 Z holds
( r (#) f is_partial_differentiable_on1 Z & (r (#) f) partial1| Z = r (#) () )
proof end;

theorem :: NDIFF_7:50
for X, Y, W being RealNormSpace
for Z being Subset of [:X,Y:]
for r being Real
for f being PartFunc of [:X,Y:],W st Z is open & f is_partial_differentiable_on2 Z holds
( r (#) f is_partial_differentiable_on2 Z & (r (#) f) partial2| Z = r (#) () )
proof end;

theorem LMX1: :: NDIFF_7:51
for X, Y, W being RealNormSpace
for Z being Subset of [:X,Y:]
for f being PartFunc of [:X,Y:],W st f is_differentiable_on Z holds
( f | Z is_continuous_on Z iff (f * ((IsoCPNrSP (X,Y)) ")) | (((IsoCPNrSP (X,Y)) ") " Z) is_continuous_on ((IsoCPNrSP (X,Y)) ") " Z )
proof end;

theorem :: NDIFF_7:52
for X, Y, W being RealNormSpace
for Z being Subset of [:X,Y:]
for f being PartFunc of [:X,Y:],W st Z is open holds
( f is_partial_differentiable_on1 Z & f is_partial_differentiable_on2 Z & f partial1| Z is_continuous_on Z & f partial2| Z is_continuous_on Z iff ( f is_differentiable_on Z & f `| Z is_continuous_on Z ) )
proof end;

format: plain


text:
## Notes

• Describing knowledge of a system probabilistically, having an appropriate prior probability, know how to weigh new evidence, and following Bayes’s rule to compute the revised distribution.
• How Yoshi sends signals about her food preferences.
• Prob x given y
• Posterior probability and prior probability
• Distribution after and distribution before
• Prior times likelihood is posterior
• Converges quickly to new posterior


text:
# Cloud services to backtest minute data

#### donny

Hi Quantnet,

My current tasks is to backtest a 5 min bar trading strategy over 10 years. It uses regression and as expected, it's very slow. At 1 hour needed for a 1 asset 10 year result, it's obvious that I need more computational power. I have a few virtual machines at my disposal but they won't cut it.

Question: Are there any free cloud services where I can rent and backtest my strategies? Something like AWS and Azure. Emphasis is free. Scale is a priority here, so really I need like 100 free virtual machines to order to say that implementation is worth while.

Relatedly, have any of you wrote your own linear regression function that performs orders of magnitude faster than a library? I'm using accord-framework.net. I also believe third party libraries are already optimized to be fastest.

Donny

Last edited:

#### BurgerKing

Actually for simple rolling linear regression of a fixed number of variables, you can implement it on CUDA C. It will speed up your regression at least an order of magnitude.

#### donny

Thanks everyone. I heard of CUDA before. I think that's what I was looking for.

Out of the multitude of options - Cuda, own C# implementation, FPGA, Matlab, R - looks like CUDA is the way to go.

I trust your word on the CUDA implementation and look into it.

#### BurgerKing

Well I actually wrote something like that a few years ago. Just paste it here in case it may help.

C++:
#include <cuda_runtime.h>

#define BLOCK_SIZE 32
__global__ void RollingSimpleLinearRegression_kernel(float* x_dev,float* y_dev,float* beta_dev, float* alpha_dev, float* residual_dev, int n, int window){
float Sx=0;
float Sy=0;
float Sxx=0;
float Sxy=0;
float Syy=0;

//First regresssion

float x=0;
float y=0;

for (size_t i=0;i<window;i++){
Sx+=x;
Sy+=y;
Sxx+=x*x;
Sxy=x*y;
Syy=y*y;
}
float beta=(window*Sxy-Sx*Sy)/(n*Sxx-Sx*Sx);
float alpha=1.0f/window*Sy-beta*Sx*1.0f/n;
float residual=0;

if (dataId < n){
x = x_dev[dataId];
y = y_dev[dataId];
residual = y - alpha - beta*x;
//Output
beta_dev[dataId] = beta;
alpha_dev[dataId] = alpha;
residual_dev[dataId] = residual;
//Update metrics
Sx += x - lastX;
Sy += y - lastY;
Sxx += x*x - lastX*lastX;
Sxy = x*y - lastX*lastY;
Syy = y*y - lastY*lastY;
lastY = y;
lastX = x;
beta = (window*Sxy - Sx*Sy) / (n*Sxx - Sx*Sx);
alpha = 1.0f / window*Sy - beta*Sx*1.0f / n;
}
}

}
void RollingSimpleLinearRegression(float* x,float* y,float* beta, float* alpha, float* residual, int n, int window){
cudaSetDevice(0);
cudaFree(0);

cudaStream_t stream;
cudaError_t result;

result = cudaStreamCreate ( &stream) ;

if (result!=cudaSuccess){
PrintError("Create stream");
return;
}
size_t vecSzInBytes_float=n * sizeof(float);

//Allocate vectors in device memory
float* x_dev=0;
float* y_dev=0;
float* alpha_dev=0;
float* beta_dev=0;
float* residual_dev=0;

cudaMalloc(&x_dev               ,vecSzInBytes_float);
cudaMalloc(&y_dev               ,vecSzInBytes_float);
cudaMalloc(&alpha_dev            ,vecSzInBytes_float);
cudaMalloc(&beta_dev            ,vecSzInBytes_float);
cudaMalloc(&residual_dev        ,vecSzInBytes_float);

cudaMemset(alpha_dev           ,0,vecSzInBytes_float);
cudaMemset(beta_dev               ,0,vecSzInBytes_float);
cudaMemset(residual_dev           ,0,vecSzInBytes_float);

cudaMemcpyAsync(x_dev          ,x,vecSzInBytes_float,cudaMemcpyHostToDevice,stream);
cudaMemcpyAsync(y_dev          ,y,vecSzInBytes_float,cudaMemcpyHostToDevice,stream);

cudaStreamSynchronize(stream);

PrintError("cudaMemcpyAsync and cudaMemset");
//Calculate number of blocks
RollingSimpleLinearRegression_kernel<<<noBlock,BLOCK_SIZE>>>(x_dev,y_dev,beta_dev,alpha_dev,residual_dev,n,window);
cudaStreamSynchronize(stream);
//Copy back to host
cudaMemcpyAsync(beta            ,beta_dev,vecSzInBytes_float,cudaMemcpyDeviceToHost,stream);
cudaMemcpyAsync(alpha            ,alpha_dev,vecSzInBytes_float,cudaMemcpyDeviceToHost,stream);
cudaMemcpyAsync(residual        ,residual_dev,vecSzInBytes_float,cudaMemcpyDeviceToHost,stream);

cudaStreamSynchronize(stream);

//Free memory
cudaFree(x_dev);
cudaFree(y_dev);
cudaFree(beta_dev);
cudaFree(alpha_dev);
cudaFree(residual_dev);

cudaStreamSynchronize(stream);
PrintError("End function");
}

#### donny

Any idea why there isn't a simple linear regression library for CUDA?

I'm been searching the internet and only found -
https://devtalk.nvidia.com/default/topic/494482/linear-regression-cuda-code/

I'm being pushed for results so if it'll take time, I need to go back to my manager and propose a tangent from our infrastructure to develop on CUDA, which may not be taken well.

Did a few more searches. Unless there's no such thing. I found something like this: Home

Basically, can I just go
CUDALinearModel aModel = new CUDALinearModel()
aModel.Regress(inputs, outputs)

Or I'll have to learn this CUDA thing from scratch.

Last edited:

#### BurgerKing

Last time I checked there was no such library widely available (maybe there is a proprietary one). And also it will be quite inefficient as you will have to spend a round-trip to copy data to GPU memory, linear-regressing it, then copy it back for each regression, i.e. no batch regression. If you only do simple linear regression then I think my codes are ok. Otherwise, you will have to do something along the line of batch QR decomposition to speed up your multiple regression.

#### donny

Thank you BurgerKing. Actually, I did a quick prototype on Matlab to backtest 10 years 5 mins with linear regression. You know what, it's obviously faster. So quick question to confirm:

In general, which is faster in linear regression - scientific languages (Matlab, R) or C# with library Accord.NET Machine Learning Framework

A discussion with my colleague said that scientific languages are meant for that sort of work. If what seems to be a 10x speed increase is true, I can quickly switch backtesting to Matlab, check results, then recode the strategy in C# for execution.

#### BurgerKing

Actually, if you only do regression, then MATLAB is highly optimized for that kind of work, and is likely faster than the C# codes (I have no idea how good is R though). 10x is a bit too much, but maybe 2-3 times. I think you can try a simple prototype with MATLAB parfor command first with all your CPU cores. If still not enough then either rack-up a MATLAB computing cluster or code a MATLAB mex file to leverage CUDA in C, or both.

I think the trick is when you backtest your strategy, it's likely that you will have to do a lot of rolling regression with 5 minute increment, so try to reuse/online update the past estimation instead of doing the whole regression again.

#### donny

I did a quick prototype to test speed for C#, Matlab and R. The set up is regress y ~ x1 + x2 where y, x1 and x2 are each 8,000 randomly generated numbers. Then repeat the regression 5,000 times.

Here's what I got. I'm sharing it with you since everyone else in Quantnet seems quiet.

Matlab: 17 seconds.
R: 55 seconds.
C#: 24 seconds.

Of course, you have to consider the time taken to generate the random numbers. I decided on new random numbers each pass just to be sure the language does a new regression in case the previous one was saved.

Looks like Matlab it is.

Though the problem I see here is that I'm not sure the differences are amplified if I used actual data and not random data. The scientific library might be able to pick up on the commonalities at each pass and optimized further.

I guess that's why I'm a quantitative research or not a software engineer. Thanks for the good discussion. At least I have something to back to my boss with.

#### ExSan

what about bitcoin mining using the cloud ?

#### BurgerKing

@donny I think it should be faster if you are using real data, cos the data will be pre-allocated in memory and MATLAB memory performance is actually quite good for a scripting language.

@ExSan IMO, cloud computing has very poor price/performance ratio, which means you won't be able to profit from mining using cloud. Most people/companies uses cloud because it saves them maintenance and setup cost, not because of its performance.

#### pingu

what about bitcoin mining using the cloud ?
This is a money losing proposition. Even using ASICs (which I have done) won't justify the cost today. (It didn't justify the cost a year ago when I did it but it was a fun project)

#### ExSan

This is a money losing proposition. Even using ASICs (which I have done) won't justify the cost today. (It didn't justify the cost a year ago when I did it but it was a fun project)
ASICs ?

#### pingu

ASICs ?
Application-specific integrated circuit - Wikipedia, the free encyclopedia
You can buy specific circuits to mine bitcoin. They have been around sort of cheap for a while. You can buy highly sophisticated ones or small ones depending on your taste. These are specifically designed to only solve the bitcoin problem so they don't waste time/energy in anything else. If you aren't doing ASIC miners, you can pretty much kiss the odds of finding a block goodbye.

Mining hardware comparison - Bitcoin Wiki
Non-specialized hardware comparison - Bitcoin Wiki
Bitcoin Mining Hardware - ASIC Bitcoin Miner - Butterfly Labs
Can Hobbyist Bitcoin Miners Still Make a Buck?
Blockchain Smashers

Last edited:

#### ExSan

Application-specific integrated circuit - Wikipedia, the free encyclopedia
You can buy specific circuits to mine bitcoin. They have been around sort of cheap for a while. You can buy highly sophisticated ones or small ones depending on your taste. These are specifically designed to only solve the bitcoin problem so they don't waste time/energy in anything else. If you aren't doing ASIC miners, you can pretty much kiss the odds of finding a block goodbye.

Mining hardware comparison - Bitcoin Wiki
Non-specialized hardware comparison - Bitcoin Wiki
Bitcoin Mining Hardware - ASIC Bitcoin Miner - Butterfly Labs
Can Hobbyist Bitcoin Miners Still Make a Buck?
Blockchain Smashers
thanks a lot !

#### donny

Hmmm, I repeated the test again using actual prices and the improvement wasn't as much. For linear regression of 8000 data points, repeated 5000 times using real AUDUSD and ES prices, Matlab took 70% of the time C# took to perform it. R was slower than either Matlab and C#.

And I went to my boss and said linear regression done on Matlab was faster than C#, and he was shocked. Argh.

#### pingu

Hmmm, I repeated the test again using actual prices and the improvement wasn't as much. For linear regression of 8000 data points, repeated 5000 times using real AUDUSD and ES prices, Matlab took 70% of the time C# took to perform it. R was slower than either Matlab and C#.

And I went to my boss and said linear regression done on Matlab was faster than C#, and he was shocked. Argh.
did you use loops in your R version?

#### diegosanaz

##### BU MSMF
yeah, there are many tricks that could be used in R to improve performance, such as using some parallel computing library.

#### donny

In R, you can't vectorize regression where each regression uses a vector in itself.

Or at least my knowledge in R believe it can't be done without loops.

The problem is loop X times where each time is a regression of Y points.

Replies
2
Views
5K
Replies
4
Views
2K
Replies
0
Views
1K
Replies
0
Views
1K
Replies
11
Views
9K


text:
# zbMATH — the first resource for mathematics

## Zhang, Jianwen

Compute Distance To:
 Author ID: zhang.jianwen Published as: Zhang, J.; Zhang, J. W.; Zhang, Jian W.; Zhang, Jian-Wen; Zhang, Jianwen
 Documents Indexed: 157 Publications since 1986
all top 5

#### Co-Authors

 8 single-authored 9 Zhao, Junning 8 Wang, Danxia 7 Chai, Yuzhen 7 Liu, Youjun 7 Yan, Jurang 6 Xu, Xinying 5 Jiang, Song 5 Li, Qingshi 4 Hao, Huiqin 4 Liu, Shengquan 4 Yang, Guitong 4 Zhang, Jianguo 3 Chen, Mingtao 3 Niu, Lifang 3 Wang, Yinzhu 3 Wu, Runheng 3 Xie, Feng 3 Ye, Xia 2 Cai, Zhongmin 2 Li, Qinshi 2 Ren, Yonghua 2 Zhang, Haifeng 2 Zhang, Peixin 1 Cheng, Yongling 1 Ding, Xiaxia 1 Du, Qingqing 1 Du, Xiaojiao 1 Fang, Yi 1 Feng, Tao 1 Guo, Rui 1 Guo, Yong 1 Han, Xiaoyou 1 He, Ming 1 Huang, Bin 1 Jia, Hongen 1 Jia, Tingting 1 Lai, Suhua 1 Li, Hailiang 1 Li, Jing 1 Li, Jinkai 1 Li, Qinghsi 1 Liu, Xinguo 1 Lv, Jiawei 1 Rong, Xiaoliang 1 Si, Xin 1 Song, Xingxing 1 Sui, Lili 1 Wang, Fei 1 Wang, Lin 1 Wang, Zheng 1 Xu, Ce 1 Xu, Zhonghai 1 Yang, Yingyue 1 Yao, Huazhen 1 Yu, Haibo 1 Zeng, Yanting 1 Zhang, Changshui 1 Zhang, Lingmei 1 Zhang, Mingyu 1 Zhang, Sufang 1 Zhang, Wen 1 Zhang, Wenlin 1 Zhao, Chong 1 Zhao, Xiaokui 1 Zheng, Tingting 1 Zou, Jietao
all top 5

#### Serials

 5 Journal of Differential Equations 5 Mathematics in Practice and Theory 4 Nonlinear Analysis. Theory, Methods & Applications. Series A: Theory and Methods 4 Mathematical Problems in Engineering 4 International Journal of Pure and Applied Mathematics 4 Journal of North University of China. Natural Science Edition 3 Journal of Mathematical Analysis and Applications 3 Journal of Engineering Mathematics (Xi’an) 3 Acta Physica Sinica 3 Mathematica Applicata 3 SIAM Journal on Mathematical Analysis 3 Discrete Dynamics in Nature and Society 3 Nonlinear Analysis. Real World Applications 2 Nonlinearity 2 ZAMP. Zeitschrift für angewandte Mathematik und Physik 2 Journal of Xiamen University. Natural Science 2 Journal of Systems Science and Mathematical Sciences 2 M$$^3$$AS. Mathematical Models & Methods in Applied Sciences 2 Communications in Mathematical Sciences 2 Boundary Value Problems 1 Journal of Mathematical Physics 1 Colloquium Mathematicum 1 Journal of Computational and Applied Mathematics 1 Acta Mathematicae Applicatae Sinica 1 Journal of Mathematical Research & Exposition 1 Chinese Annals of Mathematics. Series A 1 Journal of Biomathematics 1 Applied Mathematics Letters 1 Science in China. Series A 1 Applications of Mathematics 1 Journal of Dynamics and Differential Equations 1 Discrete and Continuous Dynamical Systems 1 Nonlinear Dynamics 1 Abstract and Applied Analysis 1 Acta Mathematica Scientia. Series A. (Chinese Edition) 1 Journal of Mathematical Fluid Mechanics 1 Communications in Nonlinear Science and Numerical Simulation 1 Discrete and Continuous Dynamical Systems. Series B 1 Acta Mathematica Scientia. Series B. (English Edition) 1 Bulletin of the Malaysian Mathematical Sciences Society. Second Series 1 Communications on Pure and Applied Analysis 1 Periodical of Ocean University of China 1 Journal of Lanzhou University of Technology 1 International Journal of Number Theory 1 Systems Engineering and Electronics 1 Chinese Journal of Engineering Mathematics
all top 5

#### Fields

 70 Partial differential equations (35-XX) 39 Fluid mechanics (76-XX) 12 Mechanics of deformable solids (74-XX) 10 Ordinary differential equations (34-XX) 6 Numerical analysis (65-XX) 5 Dynamical systems and ergodic theory (37-XX) 4 Operator theory (47-XX) 3 Optics, electromagnetic theory (78-XX) 2 Computer science (68-XX) 2 Astronomy and astrophysics (85-XX) 1 Number theory (11-XX) 1 Real functions (26-XX) 1 Several complex variables and analytic spaces (32-XX) 1 Special functions (33-XX) 1 Integral equations (45-XX) 1 Statistics (62-XX) 1 Biology and other natural sciences (92-XX) 1 Information and communication theory, circuits (94-XX)


text:
# NAG CL Interfaces13acc (integral_cos)

Settings help

CL Name Style:

## 1Purpose

s13acc returns the value of the cosine integral
 $Ci(x)=γ+lnx+∫0xcosu-1udu, x>0$
where $\gamma$ denotes Euler's constant.

## 2Specification

 #include
 double s13acc (double x, NagError *fail)
The function may be called by the names: s13acc, nag_specfun_integral_cos or nag_cos_integral.

## 3Description

s13acc calculates an approximate value for $\mathrm{Ci}\left(x\right)$.
For $0 it is based on the Chebyshev expansion
 $Ci(x)=lnx+∑r=0′arTr(t),t=2 (x16) 2-1.$
For $16 where the value of ${x}_{\mathrm{hi}}$ is given in the Users' Note for your implementation,
 $Ci(x)=f(x)sinxx-g(x)cosxx2$
where $f\left(x\right)=\underset{r=0}{{\sum }^{\prime }}\phantom{\rule{0.25em}{0ex}}{f}_{r}{T}_{r}\left(t\right)$ and $g\left(x\right)=\underset{r=0}{{\sum }^{\prime }}\phantom{\rule{0.25em}{0ex}}{g}_{r}{T}_{r}\left(t\right)$, $t=2{\left(\frac{16}{x}\right)}^{2}-1$.
For $x\ge {x}_{\mathrm{hi}}$, $\mathrm{Ci}\left(x\right)=0$ to within the accuracy possible (see Section 7).

## 4References

NIST Digital Library of Mathematical Functions

## 5Arguments

1: $\mathbf{x}$double Input
On entry: the argument $x$ of the function.
Constraint: ${\mathbf{x}}>0.0$.
2: $\mathbf{fail}$NagError * Input/Output
The NAG error argument (see Section 7 in the Introduction to the NAG Library CL Interface).

## 6Error Indicators and Warnings

NE_ALLOC_FAIL
Dynamic memory allocation failed.
See Section 3.1.2 in the Introduction to the NAG Library CL Interface for further information.
NE_INTERNAL_ERROR
An internal error has occurred in this function. Check the function call and any array sizes. If the call is correct then please contact NAG for assistance.
See Section 7.5 in the Introduction to the NAG Library CL Interface for further information.
NE_NO_LICENCE
Your licence key may have expired or may not have been installed correctly.
See Section 8 in the Introduction to the NAG Library CL Interface for further information.
NE_REAL_ARG_LE
On entry, ${\mathbf{x}}=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{x}}>0.0$.
The function has been called with an argument less than or equal to zero for which $\mathrm{Ci}\left(x\right)$ is not defined.

## 7Accuracy

If $E$ and $\epsilon$ are the absolute and relative errors in the result and $\delta$ is the relative error in the argument then in principle these are related by
 $|E|≃ |δcosx|and  |ε|≃ | δ cosx Ci(x) | .$
That is accuracy will be limited by machine precision near the origin and near the zeros of $\mathrm{cos}x$, but near the zeros of $\mathrm{Ci}\left(x\right)$ only absolute accuracy can be maintained.
The behaviour of this amplification is shown in Figure 1.
For large values of $x$, $\mathrm{Ci}\left(x\right)\sim \frac{\mathrm{sin}x}{x}$, therefore, $\epsilon \sim \delta x\mathrm{cot}x$ and since $\delta$ is limited by the finite precision of the machine it becomes impossible to return results which have any relative accuracy. That is, when $x\ge 1/\delta$ we have that $|\mathrm{Ci}\left(x\right)|\le 1/x\sim E$ and hence is not significantly different from zero.
Hence ${x}_{\mathrm{hi}}$ is chosen such that for values of $x\ge {x}_{\mathrm{hi}}$, $\mathrm{Ci}\left(x\right)$ in principle would have values less than the machine precision and so is essentially zero.

## 8Parallelism and Performance

s13acc is not threaded in any implementation.

None.

## 10Example

This example reads values of the argument $x$ from a file, evaluates the function at each value of $x$ and prints the results.

### 10.1Program Text

Program Text (s13acce.c)

### 10.2Program Data

Program Data (s13acce.d)

### 10.3Program Results

Program Results (s13acce.r)


text:
## anonymous 4 years ago How would I find the least common multiples for these? 2/7 5/9

since 7 is prime it has no common factor with 9, so assuming you mean the least common multiple of 7 and 9 it is $7\times 9=63$


text:
Monk and Fredo
Tag(s):

## Math, Medium, Medium

Problem
Editorial
Analytics

Fredo and you are talking about a movie that you have recently watched while Monk is busy teaching Number Theory. Sadly, Monk caught Fredo talking to you and asked him to answer his question in order to save himself from punishment. The question says:

Given two weights of $a$ and $b$ units, in how many different ways you can achieve a weight of $d$ units using only the given weights? Any of the given weights can be used any number of times (including $0$ number of times).

Since Fredo is not able to answer the question, he asked you to help him otherwise he will get punished.

Note: Two ways are considered different if either the number of times $a$ is used or number of times $b$ is used is different in the two ways.

Input Format:

The first line of input consists of an integer $T$ denoting the number of test cases.
Each test case consists of only one line containing three space separated integers $a$, $b$ and $d$.

Output Format:
For each test case, print the answer in a separate line.

Constraints:

$1 \le T \le 10^5$
$1 \le a < b \le 10^9$
$0 \le d \le 10^9$

SAMPLE INPUT
4
2 3 7
4 10 6
6 14 0
2 3 6

SAMPLE OUTPUT
1
0
1
2

Explanation

Test case $1$:
$7$ can only be achived by using $2$ two times and $3$ one time.

Test case $2$:
$6$ can't be achieved by using $4$ and $10$. So, $0$ ways are there.

Test case $3$:
$0$ can be achieved by using $0$ times $6$ and $0$ times $14$. So, there is only one way,

Test case $4$:
$6$ can be achieved by using $2$ three times or $3$ two times. So, there are two different ways of getting $6$.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Scala 2.11.8, Swift, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

CodeMonk (Number Theory Part I)

OTHER PROBLEMS OF THIS CHALLENGE
• Math > Number Theory
• Math > Number Theory
• Math > Number Theory
• Math > Number Theory


text:
# [l2h] Unwanted, black, line segments under some images corresponding to LaTeX commands probably like \dot{\vec{r}}

Pat Somerville l_pat_s at hotmail.com
Tue May 11 07:56:14 CEST 2010

Hello. Using the year-2002 version of LaTeXHTML version 1.70 in the ouput, .html file I have horizontal, black, line segments under what correspond to probably \dot{\vec{r}} and \dot{\vec{v}} in the corresponding LaTeX, .tex file for some equations. I saw the unwanted, black, line segments in a Konqueror Web browser. The command \dot{x} corresponds to a dot above the variable x, which in turn corresponds to the time derivative of x. Last year I followed Shigeharu Takeno's kindly provided advice of commenting out the line reading

\$DVIPSOPT.= " -Ppdf";

in the LaTeX configuration file l2hconf.pm. I probably still have that line commented out. That got rid of some unwanted, black, line segments last year associated with some Portable Network Graphics (PNG) images. But last year I probably did not try to put a dot on top of a vector symbol, as in \dot{\vec{r}}. I have been using a latex2html command of the form "latex2html -nonavigation -no_math -html_version 3.2,math -split 0 Myfile.tex," with Myfile.tex being a fictitious, .tex file name. How can I get rid of the unwanted, black, line segments this time? If necessary, as a "workaround" solution I could probably use the d/dt notation instead of the dot notation for the time derivative.

Pat
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://tug.org/pipermail/latex2html/attachments/20100511/8cac9c61/attachment.html>


text:
# CERN Published Articles

Ultimi arrivi:
2021-01-22
11:34
 Optimising the benefits from research institutes / Lagrange, Thierry (CERN) 2020 In : The economics of big science, pp.39-44

2021-01-22
11:30
 Rethinking the socio-economic value of big science : lessons from the FCC study / Gutleber, Johannes (CERN) 2020 In : The economics of big science, pp.45-51

2021-01-22
06:27
 A novel approach to seamless simulations of compact hadron therapy systems for self-consistent evaluation of dosimetric and radiation protection quantities / Hernalsteens, C (U. Brussels (main) ; CERN) ; Tesse, R (U. Brussels (main)) ; Boogert, S T (Royal Holloway, U. of London) ; Flandroy, Q (IBA, Louvain-la-Neuve) ; Fuentes, C (IBA, Louvain-la-Neuve) ; Gnacadja, E (U. Brussels (main)) ; Nevay, L J (Royal Holloway, U. of London) ; Pauly, N (U. Brussels (main)) ; Ramoisiaux, E (U. Brussels (main)) ; Shields, W (Royal Holloway, U. of London) et al. Hadron therapy installations are evolving towards more compact systems that require higher-quality beams for advanced treatment modalities such as proton flash and arc therapy. Therefore the accurate modelling of present and next-generation systems poses new challenges where the simulations require both magnetic beam transport and particle-matter interactions. [...] 2020 - 7 p. - Published in : EPL 132 (2020) 50004 Fulltext: PDF;

2021-01-22
06:27
 Extended Scalar Sectors / Steggemann, Jan (CERN ; LPHE, Lausanne) Extended scalar sectors appear in various extensions of the Standard Model of particle physics, such as supersymmetric models. They are also generic extensions of the Standard Model and can address a number of its shortcomings. [...] 2020 - 29 p. - Published in : Ann. Rev. Nucl. Part. Sci. 70 (2020) 197-223 Fulltext: PDF;

2021-01-22
06:27
 The Method of Temperature Resistivity Creation of the Compact Precision Laser Inclinometer / Budagov, J (Dubna, JINR) ; Di Girolamo, B (CERN) ; Lyablin, M (Dubna, JINR) For the Precision Laser Inclinometer (PLI) temperature resistivity increase the essential design innovations have been developed and introduced in the PLI accepted design scheme. The proposed methods of the temperature resistivity guarantee—as shown experimentally—the achievement of a long term PLI sensitivity of 2.8 × 10$^{–11}$ rad for allowed ±0.1°С variation of temperature of surrounding environment.. 2020 - 7 p. - Published in : Phys. Part. Nucl. Lett. 17 (2020) 931-937

2021-01-22
06:27
 The Compact Nanoradian Precision Laser Inclinometer—an Innovative Instrument for the Angular Microseismic Isolation of the Interferometric Gravitational Antennas / Budagov, J (Dubna, JINR) ; Di Girolamo, B (CERN) ; Lyablin, M (Dubna, JINR) The conceptual new design of the Precision Laser Inclinometer (PLI) is proposed and developed what resulted in creation of compact instrument for its possible use in a restricted vacuum volume of sensitive elements of Gravitational Wave Interferometric Antennas. It is shown that the use of a position sensitive method—the dividing plates method—for the detection of angular inclination of laser beams, allows to reduce the dimensions of the PLI to a cube of 11 × 11 × 15 cm$^{3}$ or to a cylinder with a diameter of 15 cm and a height of 11 cm. [...] 2020 - 15 p. - Published in : Phys. Part. Nucl. Lett. 17 (2020) 916-930

2021-01-22
06:27
 Dynamics of the interaction of dust particles with the LHC beam / Lindstrom, B (CERN ; Uppsala U.) ; Bélanger, P (CERN ; TRIUMF) ; Gorzawski, A (CERN ; Malta U.) ; Kral, J (CERN ; Prague, Tech. U.) ; Lechner, A (CERN) ; Salvachua, B (CERN) ; Schmidt, R (CERN) ; Siemko, A (CERN) ; Vaananen, M (CERN) ; Valuch, D (CERN) et al. Micrometer-sized dust particles present in the Large Hadron Collider (LHC) beam pipe are believed to have caused many thousands of sporadic beam loss events around the LHC. These so-called unidentified falling objects (UFOs) have been under continuous study since the start of high intensity beam operation in the LHC due to their impact on the LHC availability: 139 beam dumps and 12 magnet quenches during Run II (2015–2018) alone. [...] 2020 - 14 p. - Published in : Phys. Rev. Accel. Beams 23 (2020) 124501 Fulltext from Publisher: PDF;

2021-01-22
06:27
 Temperature-Dependent Field Emission and Breakdown Measurements Using a Pulsed High-Voltage Cryosystem / Jacewicz, Marek (Uppsala U.) ; Eriksson, Johan (Uppsala U.) ; Ruber, Roger (Uppsala U.) ; Calatroni, Sergio (CERN) ; Profatilova, Iaroslava (CERN) ; Wuensch, Walter (CERN) A variable-temperature pulsed high-voltage system has been constructed and a series of high-field measurements on copper electrodes have been carried out. The measurements are made at ambient to cryogenic temperatures and include conditioning, breakdown threshold, and field emission. [...] 2020 - 6 p. - Published in : Phys. Rev. Applied 14 (2020) 061002 Fulltext: PDF;

2021-01-22
06:27
 EuPRAXIA Conceptual Design Report / Assmann, R W (DESY) ; Weikum, M K (DESY) ; Akhter, T (INFN, Naples) ; Alesini, D (Frascati) ; Alexandrova, A S (Cockcroft Inst. Accel. Sci. Tech. ; U. Liverpool (main)) ; Anania, M P (Frascati) ; Andreev, N E (ITAE, Moscow ; Moscow, MIPT) ; Andriyash, I (Weizmann Inst.) ; Artioli, M (ENEA, Bologna) ; Aschikhin, A (DESY) et al. This report presents the conceptual design of a new European research infrastructure EuPRAXIA. The concept has been established over the last four years in a unique collaboration of 41 laboratories within a Horizon 2020 design study funded by the European Union. [...] 2020 - 610 p. - Published in : Eur. Phys. J. Spec. Top. 229 (2020) 3675-4284 Fulltext from Publisher: PDF;

2021-01-22
06:27
 Reducing Beam-Related Background on Forward Physics Detectors Using Crystal Collimation at the Large Hadron Collider / Mirarchi, D (Manchester U. ; CERN) ; Avati, V (AGH-UST, Cracow ; CERN) ; Bruce, R (CERN) ; Butcher, M (CERN) ; D'Andrea, M (CERN ; U. Padua (main)) ; Di Castro, M (CERN) ; Deile, M (CERN) ; Dziedzic, B (Cracow, INP) ; Hiller, K (DESY) ; Jakobsen, S (CERN) et al. Beam collimation in high-energy colliders is customarily carried out by means of massive amorphous absorbers surrounding the circulating beam. Several studies were performed in the last decades to establish an innovative collimation technique that relies on particle deflection by means of channeling between crystalline planes of a bent crystal. [...] 2020 - 20 p. - Published in : Phys. Rev. Applied 14 (2020) 064066 Fulltext: PDF;


text:
## 0.4 Miscellaneous Information

### 0.4.1 R Packages

This book uses the following contributed R packages that are currently available from CRAN, the Comprehensive R Archive Network:

• devtools
• ggplot2
• mosaicData
• R6
• tidyverse

If you are working on the Georgetown College R Studio Server then they are already installed for you. If you have your own installation then you can get them via the install.packages() function, e.g.,

install.packages("devtools")

In addition we use two packages from the author’s Github repositories:

• bcscr (functions and data sets to accompany the text)
• tigerData (data sets used in examples and exercises)

If you aren’t working on the R Studio Server at Georgetown College then you may have to install them yourself, as follows:

devtools::install_github("homerhanumat/bcscr")
devtools::install_github("homerhanumat/tigerData")

### 0.4.2 Typographical Conventions

Computer code, whether within a line of text or as displayed text, appears like this: code snippet.

Identifiers and are represented as is (e.g., variableName, if, else, while, etc.) except for the names of functions, which are followed by a pair of parentheses in order to stress their status as functions. Thus we write length() for the length-function.

Displayed text representing output to the console appears with double hash-tags at the beginning of each line, thus:

## R is free software and comes with ABSOLUTELY NO WARRANTY.
## You are welcome to redistribute it under certain conditions.
## Type 'license()' or 'licence()' for distribution details.

The hash-tags themselves are not present in the output itself.

Names of R-package are in boldface, thus: package devtools.

Terms are italicized when they are first introduced, e.g.: “R follows a set of internal rules to coerce some of the values to a new type in such a way that all resulting values are of the same type.” Italicization can also indicate emphasis.


text:
# paste

0th

Percentile

##### Concatenate Strings

Concatenate vectors after converting to character.

Keywords
character
##### Usage
paste (…, sep = " ", collapse = NULL)
paste0(…, collapse = NULL)
##### Arguments

one or more R objects, to be converted to character vectors.

sep

a character string to separate the terms. Not NA_character_.

collapse

an optional character string to separate the results. Not NA_character_.

##### Details

paste converts its arguments (via as.character) to character strings, and concatenates them (separating them by the string given by sep). If the arguments are vectors, they are concatenated term-by-term to give a character vector result. Vector arguments are recycled as needed, with zero-length arguments being recycled to "".

Note that paste() coerces NA_character_, the character missing value, to "NA" which may seem undesirable, e.g., when pasting two character vectors, or very desirable, e.g.in paste("the value of p is ", p).

paste0(…, collapse) is equivalent to paste(…, sep = "", collapse), slightly more efficiently.

If a value is specified for collapse, the values in the result are then concatenated into a single string, with the elements being separated by the value of collapse.

##### Value

A character vector of the concatenated values. This will be of length zero if all the objects are, unless collapse is non-NULL in which case it is a single empty string.

If any input into an element of the result is in UTF-8 (and none are declared with encoding "bytes", (see Encoding), that element will be in UTF-8, otherwise in the current encoding in which case the encoding of the element is declared if the current locale is either Latin-1 or UTF-8, at least one of the corresponding inputs (including separators) had a declared encoding and all inputs were either ASCII or declared.

If an input into an element is declared with encoding "bytes", no translation will be done of any of the elements and the resulting element will have encoding "bytes". If collapse is non-NULL, this applies also to the second, collapsing, phase, but some translation may have been done in pasting object together in the first phase.

##### References

Becker, R. A., Chambers, J. M. and Wilks, A. R. (1988) The New S Language. Wadsworth & Brooks/Cole.

toString typically calls paste(*, collapse=", "). String manipulation with as.character, substr, nchar, strsplit; further, cat which concatenates and writes to a file, and sprintf for C like string construction.

plotmath’ for the use of paste in plot annotation.

• paste
• paste0
##### Examples
library(base) # NOT RUN { ## When passing a single vector, paste0 and paste work like as.character. paste0(1:12) paste(1:12) # same as.character(1:12) # same ## If you pass several vectors to paste0, they are concatenated in a ## vectorized way. (nth <- paste0(1:12, c("st", "nd", "rd", rep("th", 9)))) ## paste works the same, but separates each input with a space. ## Notice that the recycling rules make every input as long as the longest input. paste(month.abb, "is the", nth, "month of the year.") paste(month.abb, letters) ## You can change the separator by passing a sep argument ## which can be multiple characters. paste(month.abb, "is the", nth, "month of the year.", sep = "_*_") ## To collapse the output into a single string, pass a collapse argument. paste0(nth, collapse = ", ") ## For inputs of length 1, use the sep argument rather than collapse paste("1st", "2nd", "3rd", collapse = ", ") # probably not what you wanted paste("1st", "2nd", "3rd", sep = ", ") ## You can combine the sep and collapse arguments together. paste(month.abb, nth, sep = ": ", collapse = "; ") ## Using paste() in combination with strwrap() can be useful ## for dealing with long strings. (title <- paste(strwrap( "Stopping distance of cars (ft) vs. speed (mph) from Ezekiel (1930)", width = 30), collapse = "\n")) plot(dist ~ speed, cars, main = title) # }
Documentation reproduced from package base, version 3.4.3, License: Part of R 3.4.3

### Community examples

richie@datacamp.com at Jan 25, 2017 base v3.3.2

See [str_c()](https://www.rdocumentation.org/packages/stringr/topics/str_c) for examples of how it differs from paste0(), particularly w.r.t. handling missing values.


text:
# query-replace within LaTeX/Math

The answer below was taken from https://stackoverflow.com/a/44913296. This is the most upvoted answer there.

Unfortunately, after running the code (for example by replacing q with \theta) one encounters the following error:

match-substitute-replacement: Invalid use of ‘\’ in replacement text

Moreover, if I use \\theta instead of \theta, query-replace does not work properly, it looks outside LaTeX formula as well.

Is there a way to correct the code?

  (defun latex-replace-in-math ()
"Call query-replace-regexp' with isearch-filter-predicate' set to filter out matches outside LaTeX math environments."
(interactive)
(let ((isearch-filter-predicate
(lambda (BEG END)
(save-excursion (save-match-data (goto-char BEG) (texmathp)))))
(case-fold-search nil))
(call-interactively 'query-replace-regexp)))

• This works as expected for me: if I replace q with \\theta, only q characters inside math environments get replaced, and are replaced by \theta. This is with Emacs 28.0.50 – Tyler Mar 17 at 14:16
• @Tyler Can you test also with a document with q outside math environments? – Name Mar 17 at 15:42
• Works also for me with Emacs 27.1 and AUCTeX 13.0.4 with the following example document \documentclass{article} \begin{document} q $$q$$ \end{document} – matteol Mar 17 at 18:13
• @name I did, and it worked. q replaced inside math environment, but not outside. – Tyler Mar 17 at 18:29